← All problems

10 Lectures and 42 Open Problems — The Paley Clique Problem

For a prime p≡1(mod4)p\equiv 1\pmod 4, let Fp\mathbb F_p be the field with pp elements and let GpG_p be the Paley graph with vertex set Fp\mathbb F_p, in which distinct vertices x,yx,y are adjacent exactly when x−yx-y is a nonzero square in Fp\mathbb F_p. The condition on pp makes this an undirected graph. Write ω(Gp)\omega(G_p) for its largest clique size. The question is to determine ω(Gp)\omega(G_p) as pp ranges over these primes, and, in particular, whether the degree-4 sum-of-squares relaxation can yield an asymptotically stronger upper bound than the known square-root-scale bounds—for example, a bound O(p1/2−ε)O(p^{1/2-\varepsilon}) for some fixed ε>0\varepsilon>0. A Degree 4 Sum-of-Squares Lower Bound for the Clique Number of the Paley Graph Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs

The degree-4 SOS value, denoted SOS4(Gp)\mathrm{SOS}_4(G_p), is the maximum of ∑i=1pE~[xi]\sum_{i=1}^{p}\widetilde{\mathbb E}[x_i] over linear functionals E~:R[x1,…,xp]≤4→R\widetilde{\mathbb E}:\mathbb R[x_1,\ldots,x_p]_{\le 4}\to\mathbb R satisfying

E~[1]=1,E~[(xi2−xi)r]=0(i∈[p], deg⁡r≤2),\widetilde{\mathbb E}[1]=1,\qquad \widetilde{\mathbb E}[(x_i^2-x_i)r]=0\quad(i\in[p],\ \deg r\le 2), E~[xixjr]=0(i≠j, {i,j}∉E(Gp), deg⁡r≤2),E~[r2]≥0(deg⁡r≤2).\widetilde{\mathbb E}[x_ix_jr]=0\quad(i\ne j,\ \{i,j\}\notin E(G_p),\ \deg r\le 2),\qquad \widetilde{\mathbb E}[r^2]\ge 0\quad(\deg r\le 2).

Here R[x1,…,xp]≤4\mathbb R[x_1,\ldots,x_p]_{\le 4} denotes polynomials of degree at most 44. The constraints encode Boolean vertex indicators, prohibit selecting nonadjacent pairs, and impose positivity through degree 22. Every actual clique gives a feasible solution, so ω(Gp)≤SOS4(Gp)\omega(G_p)\le \mathrm{SOS}_4(G_p); the question is whether this relaxation gives a substantially sharper asymptotic upper bound. A Degree 4 Sum-of-Squares Lower Bound for the Clique Number of the Paley Graph

Background

Paley graphs are a classical family of pseudorandom graphs: they are regular of degree (p−1)/2(p-1)/2, and their fixed-size subgraph counts and spectrum exhibit features associated with random graphs of edge density 1/21/2. Yet their arithmetic structure is strong, and their clique number is much harder to control than these pseudorandomness properties might suggest. The problem matters in number theory as well as Ramsey theory; for example, the independence number of a Paley graph bounds the least quadratic non-residue, and the graph is isomorphic to its complement. Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs A Degree 4 Sum-of-Squares Lower Bound for the Clique Number of the Paley Graph

The square-root barrier frames the question: the spectral bound and Lovász’s ϑ\vartheta bound both give p\sqrt p, while the stronger known arithmetic upper bound improves this only by a constant factor. This has prompted work on convex relaxations of clique number. Degree-2 SOS is equivalent to the theta bound here, so degree 4 is the first level that might improve on it. A central tension is that SOS hierarchies resist substantial improvements on spectral bounds for random graphs, whereas Paley graphs have a particularly structured spectrum, with only three distinct eigenvalues. Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs A Degree 4 Sum-of-Squares Lower Bound for the Clique Number of the Paley Graph

References

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.