9
$\begingroup$

Suppose we have a countably infinite $A$ and $F_1,F_2,\cdot\cdot\cdot$ are an infinite sequence of finite sets (denoted $\left\{F_n\right\}_{n=1}^{\infty}$) such that $\bigcup\limits_{n=1}^{\infty}F_n=A$, $F_1\subset F_2\subset \cdot\cdot\cdot$ and $F_t$ is a structure of $A$ where $t$ is between one and infinity.

Core Question

I want to come up with a code that computes the following for specific $F_t$ and find the $F_t$ that maximizes the following.

$$d=\sum\limits_{X\in \mathcal{P}(\Delta F_t/||F_t||)\setminus\emptyset}\left(\prod\limits_{x\in X}x \right)$$

  • Where $\Delta{F_t}$ is a * multiset * that arranges the elements in $F_t$ from least to greatest and takes the difference between consecutive pairs.

For example, if $F_3=\left\{1,2,4,3\right\}$ then arrange the elements from least to greatest

$$\left\{1,2,3,4\right\}$$

Then get $\Delta F_3=\left\{2-1,3-2,4-3\right\}=\left\{1,1,1\right\}$

  • $||F_t||=\sum\limits_{x\in \Delta F_t}x$ normalizes the elements in $\Delta F_t$ so the sum of all the elements is $1$ (similar to a probability distribution.)

  • $\Delta F_t/||F_t||$ divides every element in $\Delta F_t$ by $||F_t||$.

  • $\mathcal{P}(\Delta F_t/||F_t||)$ takes all subsets of $\Delta F_t/||F_t||$ in a way that repeated elements are distinctive.

So for our example where $F_3=\left\{1,2,3\right\}$, $||F_3||=1+1+1=3$, $\Delta F_3/||F_3||=\left\{1/3,1/3,1/3\right\}$,

$$\mathcal{P}\left(\Delta F_3/||F_3||\right)\setminus \emptyset=\left\{\left\{1/3\right\},\left\{1/3\right\},\left\{1/3\right\},\left\{1/3,1/3\right\},\left\{1/3,1/3\right\},\left\{1/3,1/3\right\},\left\{1/3,1/3,1/3\right\}\right\}$$

hence

$$\sum\limits_{X\in \mathcal{P}(\Delta F_3/||F_3||)\setminus\emptyset}\left(\prod\limits_{x\in X}x\right)=\prod\limits_{x\in \left\{1/3\right\}} x+\prod\limits_{x\in\left\{1/3\right\}}x+\prod\limits_{x\in\left\{1/3\right\}}x+\prod\limits_{x\in\left\{1/3,1/3\right\}}x+\prod\limits_{x\in\left\{1/3,1/3\right\}}x+\prod\limits_{x\in\left\{1/3,1/3\right\}}+\prod\limits_{x\in\left\{1/3,1/3,1/3\right\}}x= 1/3+1/3+1/3+1/9+1/9+1/9+1/27=37/27$$

Example

If $A=\left\{\frac{1}{n}:n\in\mathbb{N}\right\}$ and $F_t=\left\{\frac{1}{n}:n\in\mathbb{N},n\le t\right\}$, I did the following to compute $d$:

F[t_] := F[t] = 
Sort[DeleteDuplicates[
Select[Flatten[Table[1/m, {m, 1, t}]], Between[#, {0, 1}] &]]]
F1[t_] := F1[t] = Total[Differences[F[t]]]
F2[t_] := F2[t] = Sort[Differences[F[t]]/F1[t]]
d1[t_] := d1[t] = Subsets[F2[t], {1, Length[F2[t]]}];
d[t_] := d[t] = 
  N[Total[Table[Times @@ d1[t][[s]], {s, 1, Length[d1[t]]}]]]

Once t goes beyond $20$ it takes more time to compute and even if it converges it converges extremely slow.

Is there a way we can compute my example of $d$ more efficiently? Is there a way we can generalize this for any $F_t$?

Edit: As a user pointed out, generalizing for any $F_t$ is impossible. However, I wish to compute $d$, where $A=\left\{\frac{1}{n}:n\in\mathbb{N}\right\}$, for the following $F_t$:

  1. $F_t=\left\{\frac{1}{n}:n\in\mathbb{N},n\le t\right\}$

  2. $F_t=\left\{{1}/{\left[2^t/m\right]}:m\in\mathbb{N}, m\le 2^t \right\}$ (where $[\cdot]$ is the nearest integer function)

I hope 1. and 2. will give different results for $d$.

I also wish to calculate $d$, where $A=\mathbb{Q}\cap[0,1]$, for the following:

  1. $F_t=\left\{\frac{m}{n!}: m,n\in\mathbb{N}, m\le n!\le t\right\}$

  2. $F_t=\left\{\frac{m}{n}:m,n\in\mathbb{N},m\le n\le t\right\}$

I also hope, in this case, that 1. and 2. give different results with $d$.

$\endgroup$
2
  • $\begingroup$ Is the empty set not a member of the power set in your notation? $\endgroup$ Sep 22, 2021 at 14:58
  • $\begingroup$ No but I should have used the set difference notation. $\endgroup$
    – Arbuja
    Sep 22, 2021 at 15:44

1 Answer 1

3
+50
$\begingroup$

Just a cheap observation because I did not follow the whole notation, but maybe you can use the fact that for any set $S$ (with distinct elements) $$\sum_{X \in \mathcal{P}(S)} (\prod_{x\in X} x) = \prod_{x\in S} (1+x)$$ holds.

$\endgroup$
6
  • $\begingroup$ Since $\Delta F_t/||F_t||$ is a multi-set, this equation may not work. Is there a way we can manipulate this? $\endgroup$
    – Arbuja
    Sep 22, 2021 at 14:53
  • $\begingroup$ @Arbuja It's not clear to me how you wish to handle multiplicities; are you sure it doesn't work anyway? $\endgroup$ Sep 22, 2021 at 14:58
  • $\begingroup$ I made edits, to my post. Hopefully, it clarifies how to handle multiplicities. $\endgroup$
    – Arbuja
    Sep 22, 2021 at 15:45
  • $\begingroup$ @Arbuja Thanks! Then this seems exactly the concept of multiplicities that works well with the formula I wrote. You should be able to apply it to your problem without changes, if I am not missing anything: for instance, in your example (1+1/3)(1+1/3)(1+1/3) - 1 = 37 / 27. (The -1 is to account for the missing empty set). $\endgroup$ Sep 22, 2021 at 15:52
  • $\begingroup$ Is there a name for this identity? $\endgroup$
    – Richard
    Sep 23, 2021 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.