9

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$.

Arbuja
  • 53
  • 7

1 Answers1

3

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.

Federico Poloni
  • 11,344
  • 1
  • 31
  • 59
  • Since $\Delta F_t/||F_t||$ is a multi-set, this equation may not work. Is there a way we can manipulate this? – Arbuja Sep 22 '21 at 14:53
  • @Arbuja It's not clear to me how you wish to handle multiplicities; are you sure it doesn't work anyway? – Federico Poloni Sep 22 '21 at 14:58
  • I made edits, to my post. Hopefully, it clarifies how to handle multiplicities. – Arbuja Sep 22 '21 at 15:45
  • @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). – Federico Poloni Sep 22 '21 at 15:52
  • Is there a name for this identity? – Richard Sep 23 '21 at 05:26
  • @Richard Not that I know. It follows from basic combinatorial principles; to prove it, it is sufficient to expand the RHS and note that it has $2^{|S|}$ terms that can be put in bijection with the subsets of $S$: for each subset $T \in \mathcal{P}(S)$, we obtain a term in the expansion of the RHS by taking from each parenthesis $x$ when $x\in T$ and $1$ when $x\not\in T$. – Federico Poloni Sep 23 '21 at 06:18