Chung's Paley discrepancy conjecture

About 12 years old · traced to

For primes p≡1 mod 4p\equiv1\bmod4, let χ\chi be the Legendre symbol modulo pp. Define PaleyDiscrepancy⁡[α,β]\operatorname{PaleyDiscrepancy}[\alpha,\beta] to mean that, for every sufficiently large pp,

∣∑a,b∈Sχ(a−b)∣<∣S∣2−β\left|\sum_{a,b\in S}\chi(a-b)\right|<|S|^{2-\beta}

for every S⊆FpS\subseteq\mathbb{F}_p with ∣S∣>pα|S|>p^\alpha. Chung's conjecture. For each α>0\alpha>0, there exists β=β(α)>0\beta=\beta(\alpha)>0 such that PaleyDiscrepancy⁡[α,β]\operatorname{PaleyDiscrepancy}[\alpha,\beta]. This folklore conjecture appeared as Conjecture 2.2 in Chung (1994), with a proof for α>1/2\alpha>1/2 given there, and has also been used in constructing a pseudorandom number generator. The source does not state a complete resolution for arbitrary α>0\alpha>0.

References

Primary source

Afonso S. Bandeira, Dustin G. Mixon and Joel Moreira, “A conditional construction of restricted isometries”, arXiv:1410.6457 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.