Chung's Paley discrepancy conjecture

For primes p1mod4p\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,bSχ(ab)<S2β\left|\sum_{a,b\in S}\chi(a-b)\right|<|S|^{2-\beta}

for every SFpS\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.

Sources & referencesView supporting material

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.