10 Lectures and 42 Open Problems — The Paley Clique Problem
For a prime , let be the field with elements and let be the Paley graph with vertex set , in which distinct vertices are adjacent exactly when is a nonzero square in . The condition on makes this an undirected graph. Write for its largest clique size. The question is to determine as 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 for some fixed . 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 , is the maximum of over linear functionals satisfying
Here denotes polynomials of degree at most . The constraints encode Boolean vertex indicators, prohibit selecting nonadjacent pairs, and impose positivity through degree . Every actual clique gives a feasible solution, so ; 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 , and their fixed-size subgraph counts and spectrum exhibit features associated with random graphs of edge density . 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 bound both give , 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
Progress summary
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.