Uniform-distribution conjecture for the random variable X_l(m,N)

About 8 years old · traced to 2018

Let $N\ge 3$ , and let $l$ and $m$ be positive integers such that $1\le l\le N$ , $2\le m\le N-1$ , and both $l$ and $m$ are relatively prime to $N$ . Let $X_l(m,N)$ be the random variable from Definition $1.2$ . Uniform-distribution conjecture. The random variable $X_l(m,N)$ is uniformly distributed if and only if $N$ is a prime number. The conjecture is motivated by computations and heuristic arguments: the prime case is established in the preceding discussion, while examples for small composite values of $N$ suggest that primality is also necessary.

References

Primary source

Romeo Meštrović, “On some discrete random variables arising from recent study on statistical analysis of compressive sensing”, arXiv:1803.02260 (2018).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written argument claims the conjecture is false for every odd composite size, but no independent verification was found.

The conjecture, appearing in Meštrović’s 2018 work, says that uniformity occurs exactly when $N$ is prime. The prime case is established there; the composite case was presented as conjectural.

Known results

Meštrović, 2018: the prime case is established, while the paper records supporting computations and related structural results for $X_l(m,N)$ .
For $l\ne0$ , the expected value of $X_l(m,N)$ is $0$ , with an explicit variance formula; these results do not settle the conjecture.

Posted attempt

A reader-written argument claims a complete counterexample: for every odd $N\ge3$ and every $l$ coprime to $N$ , the pair-sum variable $X_l(2,N)$ is uniform because distinct unordered pairs of $N$ th roots of unity have distinct sums. Thus $N=9$ , $l=1$ , $m=2$ would refute necessity of primality. The argument has not been independently verified.

Current status (as of August 2026): The prime case is settled, while the conjectured failure of uniformity for composite $N$ is challenged by an unverified counterexample claim and is not mathematically resolved.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

In fact, for every odd integer $N\ge3$ and every $\ell$ coprime to $N$ , the random variable $X_\ell(2,N)$ is uniformly distributed, regardless of whether $N$ is prime.

Put

\zeta=\exp\left(-\frac{2\pi i\ell}{N}\right).

Since $\gcd(\ell,N)=1$ , its powers are precisely the $N$ distinct $N$ -th roots of unity. The variable $X_\ell(2,N)$ chooses one of the

\binom N2

unordered pairs of distinct roots with equal probability.

No such pair has sum zero: otherwise its elements would be antipodal, which is impossible when $N$ is odd. Now let $z,w$ be any two unit-modulus roots with

s=z+w\ne0.

Because $\overline z=1/z$ and $\overline w=1/w$ ,

\overline s = \frac1z+\frac1w = \frac{s}{zw}.

Consequently,

zw=\frac{s}{\overline s}.

Thus the unordered pair $\{z,w\}$ is uniquely determined by its sum: its members are exactly the two roots of

T^2-sT+\frac{s}{\overline s}=0.

Therefore all $\binom N2$ pair sums are distinct, and each occurs with probability

\frac1{\binom N2}.

Taking

N=9,\qquad \ell=1,\qquad m=2

gives $36$ equally probable values although $N$ is composite. All stated hypotheses hold:

2\le m\le N-1,\qquad \gcd(\ell,N)=\gcd(m,N)=1.

More generally, every odd composite $N$ provides a counterexample.

The source's Proposition 2.1 already establishes uniformity at the allowed endpoint $m=N-1$ for every $N$ . The interior family $m=2$ above shows that excluding this endpoint would still not repair the conjecture.