1
$\begingroup$

Motivation

Suppose we have a countably infinite $A$ with order and group structures and suppose $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$, and $F_1\subset F_2\subset \cdot\cdot\cdot$

We state that $F_t$ is equidistributed in the interval $[\inf(A),\sup(A)]=[a,b]$ when for any sub-interval $[c,d]$ of $[a,b]$ we have there exists $\frac{d-c}{b-a}$ such for every arbitrarily small positive $\epsilon$ there exists a sufficiently large integer $N$ where for all $t\ge N$

$$\left|\frac{\left|F_t\cap[c,d]\right|}{|F_t|}-\frac{d-c}{b-a}\right|\le\epsilon$$

The discrepancy measures how much a structure deviates from being equidistributed in $[a,b]$. While there already have been measures for the discrepancy such as

$$\sup_{a\le c \le d \le b}\left|\frac{\left|F_t\cap[c,d]\right|}{|F_t|}-\frac{d-c}{b-a}\right|$$

The discrepancy only measures the maximum deviance of $F_t$ from equidistribution in $[a,b]$ and always converges to zero as $t$ grows larger.

Hence, we need an alternative definition to the discrepancy that converges to different values, depending on the arrangement of $F_t$

Core Question

I wish to compute my measure of deviance from equidistribution (for particular $F_t$). In my new definition, a set is equidistributed when the differences between consecutive pairs in a set are all the same.

For instance $\left\{\frac{1}{3},\frac{2}{3},\frac{3}{3}\right\}$ is equidistriubted since $\frac{2}{3}-\frac{1}{3}=\frac{3}{3}-\frac{2}{3}$ and $\left\{\frac{1}{4},\frac{2}{4},\frac{3}{4},\frac{4}{4}\right\}$ is also equidistriubted since $\frac{2}{4}-\frac{1}{4}=\frac{3}{4}-\frac{2}{4}=\frac{4}{4}-\frac{3}{4}$

We then measure the deviance from equidistribution using the following notations:

Definition:

If:

  • $\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\{\frac{1}{3},\frac{2}{3},\frac{3}{3}\right\}$ then $\Delta F_3=\left\{\frac{2}{3}-\frac{1}{3},\frac{3}{3}-\frac{2}{3}\right\}=\left\{1/3,1/3\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.)

  • $\mathcal{P}_{n}(\Delta F_t/||F_t||)$ takes all subsets of $\Delta F_t/||F_t||$ (with a cardinality of $n$) such that all elements (including repeated elements) are treated distinctively. (For example if $\Delta F_3/||F_3||=\left\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\right\}$ then $\mathcal{P}_{3}\left(\Delta F_3/||F_3||\right)=\left\{\left\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\right\}\right\}$ and $\mathcal{P}_{2}\left(\Delta F_3/||F_3||\right)=\left\{\left\{\frac{1}{3},\frac{1}{3}\right\},\left\{\frac{1}{3},\frac{1}{3}\right\},\left\{\frac{1}{3},\frac{1}{3}\right\}\right\}$)

  • $S_{n,t}=\bigcup\limits_{X\in P_{n}(\Delta F_t/||F_t||)\setminus\emptyset}\left\{\prod\limits_{x\in X}x\right\}$

  • ${\max}^{r}(S_{n,t})$ represents the $r$-th largest element in $S_{n,t}$. For example if $\Delta F_3/||F_3||=\left\{1/6,1/2,1/2\right\}$ then ${\max}^{1}\left(\Delta F_3/||F_3||\right)=\frac{1}{2}$, ${\max}^{2}\left(\Delta F_3/||F_3||\right)=\frac{1}{2}$, and ${\max}^{3}\left(\Delta F_3/||F_3||\right)=\frac{1}{6}$

  • And $$N_{n,t}=\frac{2|\Delta F_t/||F_t|||^{n-1}}{\binom{\left|\Delta F_t/||F_t||\right|}{n}+1}$$

Starting with $n=1$, we arrange the values in $S_{1,t}$ taking its greatest value, its greatest value plus the second greatest, its greatest plus second plus third greatest and continuing till we add the greatest up to the least greatest value. We then take the mean of these values giving $d_{1,t}$ and repeating this process for $n=2$ up to $n=|F_t|$. This causes the mean to converge to different values depending on the arrangement of $F_t$.

$$d_{n,t}=\frac{1}{|S_{n,t}|}\sum\limits_{p=1}^{|S_{n,t}|}\sum\limits_{r=1}^{p}{\max}^{r}\left(S_{n,t}\right)$$

If $F_t$ was completely equidistributed in $[a,b]$ we would get different values for $d_{n,t}$ for different $n$. Since want every $d_{n,t}$ to be equal, we multiply them by $$N_{n,t}=\frac{2|\; \Delta F_t/||F_t||\;|^{n-1}}{\binom{\left|\;\Delta F_t/||F_t||\;\right|}{n}+1}$$

And add them up:

$$\sum_{n=1}^{|F_t|}N_{n,t}d_{n,t}$$

Hence for every $F_t$ we want a $d(F_t,A)$ such for every arbitrarily small positive $\epsilon$ there exists a sufficiently large integer $N$ where for all $t\ge N$

$$\left|d(F_t,A)-\sum_{n=1}^{|F_t|}{N_{n,t}}d_{n,t}\right|\le\epsilon$$

or if we expand:

$$\left|d(F_t,A)-\sum_{n=1}^{|F_t|}\frac{N_{n,t}}{|S_{n,t}|}\sum\limits_{p=1}^{|S_{n,t}|}\sum\limits_{r=1}^{p}{\max}^{r}\left(S_{n,t}\right)\right|\le\epsilon$$

For a given $A$, the $F_t$ that gives $|d(F_t,A)-1|$ the smallest value is the most equidistrubuted $F_t$

Examples to compute

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] = 1/Range[1, t]
F1[t_] := F1[t] = Total[Differences[F[t]]]
F2[t_] := F2[t] = Sort[Differences[F[t]]/F1[t]]
d1[t_, n_] := d1[t, n] = Subsets[F2[t], {n}];
S[q_, t_] := 
 S[q, t] = (2 (Length[F2[t]])^(q - 1))/(Binomial[Length[F2[t]], q] + 1)
d[t_] := d[t] = 
  Sum[S[q, t] Mean[
     Table[Sum[
       RankedMax[
        Table[Times @@ d1[t, q][[s]], {s, 1, Length[d1[t, q]]}], 
        n], {n, 1, p}], {p, 1, Length[d1[t, q]]}]], {q, 1, 
    Length[F[t]]}]

But once t goes beyond $10$ it takes more time to compute, (if it converges it would do so extremely slow).

I tried getting someone to compute this on Mathematica but no one was able to answer. The moderator sent the question to computational stack exchange but someone stated that answering through programming is impossible.

Is wish for a way we can mathematically simplify this for any $F_t$ but as a user pointed out, generalizing this 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)

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

Edit: Perhaps combinatorics identities such as in this answer helps.

For any set $S$ (with distinct elements):

$$\sum_{X \in \mathcal{P}(S)} (\prod_{x\in X} x) = \prod_{x\in S} (1+x)$$

However, this time we are applying to $\mathcal{P}_{n}(S)$ instead of $\mathcal{P}(S)$

$\endgroup$
2
  • 1
    $\begingroup$ That power set is a sad story. With growth of $2^N$ that's going to you to a maximum of 30 or so elements unless you've got a lot of spare time. $\endgroup$
    – Richard
    Sep 14 at 20:26
  • $\begingroup$ @Richard Is there an unsolved math problem that (if solved) can solve my question? $\endgroup$
    – Arbuja
    Sep 14 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.