Non-sharpness of the Paley graph Shannon-capacity bounds

At least 3 years old · documented by

Let k≥3k\geq3 and let pp be a prime satisfying p≡1(modk)p\equiv1\pmod{k}. Write Θ(G)\Theta(G) for the Shannon capacity of a graph GG, and let Paley⁡k(Fp)\operatorname{Paley}_{k}(\mathbb{F}_{p}) be the generalized Paley graph over Fp\mathbb{F}_p.

Paley Shannon-capacity conjecture. There exist constants ak,bk>0a_k,b_k>0 such that, for every prime p≡1(modk)p\equiv1\pmod{k},

p12+ak≤Θ(Paley⁡k(Fp))≤p1−1k−bk.p^{\frac{1}{2}+a_k}\leq\Theta\left(\operatorname{Paley}_{k}(\mathbb{F}_{p})\right)\leq p^{1-\frac{1}{k}-b_k}.

The conjecture asserts that neither currently known bound is sharp for prime fields when k≥3k\geq3, leaving a positive power gap from both sides.

References

Primary source

Eric Naslund, “Paley Graphs and Sárközy's Theorem In Function Fields”, arXiv:2203.01293 (2022).

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.