Non-sharpness of the Paley graph Shannon-capacity bounds

Let k3k\geq3 and let pp be a prime satisfying p1(modk)p\equiv1\pmod{k}. Write Θ(G)\Theta(G) for the Shannon capacity of a graph GG, and let Paleyk(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 p1(modk)p\equiv1\pmod{k},

p12+akΘ(Paleyk(Fp))p11kbk.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 k3k\geq3, leaving a positive power gap from both sides.

Sources & referencesView supporting material

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.