25 problems

A Paley graph is the Cayley graph associated with the quadratic residues in a finite field of odd order. A graph is Ramsey when both its clique number and independence number are…

Let $p\equiv 1\pmod{4}$ be prime, let $\Phi_p$ be the Paley equiangular tight frame, and let $\delta_K=\delta_K(\Phi_p)$ denote its RIP constant of order $K$. Paley ETF RIP-constan…

Let $G$ be the Paley graph of prime order $p$, namely $G=\operatorname{Cay}(\mathbb{Z}_p,S)$ where $S$ is the set of quadratic residues modulo $p$. Let $a,b\in\mathbb{Z}_p^*$ have…

McDonald–Sahay–Wyman's conjecture. As $N\to\infty$ through the primes,

Let $r$ be an odd prime power, and let $P(r^2)$ denote the Paley graph of order $r^2$. A clique is a set of pairwise adjacent vertices, and two cliques are in the same orbit when t…

Let $q$ be an odd prime power, let $\epsilon\in\{1,3\}$ satisfy $q\equiv\epsilon\pmod 4$, and let $P(q^2)$ be the Paley graph of square order $q^2$. A maximal clique is a clique no…

Let $q$ be an odd prime power, let $\epsilon\in\{1,3\}$ satisfy $q\equiv\epsilon\pmod 4$, and let $P(q^2)$ be the Paley graph of square order $q^2$. A second-largest maximal clique…

Baker–Ebert–Hemmeter–Woldar's second-largest-clique conjecture. The clique produced by this construction is a second largest maximal clique; equivalently, there is no maximal cliqu…

Let $p$ be a prime for which the quartic residues are defined, let $F_p$ be the induced subgraph of the Paley graph $G_p$ on the nonzero fourth powers modulo $p$, and let $A_{F_p}$…

Let $p$ be prime, let $G_p$ be the Paley graph, let $g$ be a multiplicative generator of $\mathbb F_p^\times$, and let $\vartheta$ denote the Lovász theta function. Improvement con…

Asymptotic-freeness conjecture. For all sufficiently large $p$, the sequence of deterministic matrix pairs $(P_p,E_{V(G_{p,I})})$ is asymptotically free as $p\to\infty$. This inter…

Necklace character-sum conjecture. For every $k\geq1$,

Let $G_p$ be the Paley graph of prime order $p$, let $a\geq1$, and let $\mathcal I_a(G_p)$ denote the independent sets of size $a$. For $I\in\mathcal I_a(G_p)$, let $A_{G_{p,I}}$ b…

Let $G_p$ be the Paley graph of prime order $p$, let $a\geq 1$, and let $\mathcal I_a(G_p)$ be the family of independent sets of size $a$. For $I\in\mathcal I_a(G_p)$, write…

For a prime $p$, let $G_p$ be the Paley graph, let $\overline G_p$ be its complement, and write $\alpha(G_p)=\omega(\overline G_p)$ for its independence number. Here…

Let $G_p$ be the Paley graph of prime order $p$, and let $G_{p,I}$ denote a subgraph induced on the vertices extending an independent set $I$ of size $a$. Consider any sequence of…

Let $q>7$ be a prime power, and let $\mathcal{P}(q^2)$ denote the Paley graph on the finite field of order $q^2$. Let $\tau(G)$ denote the maximum order of an induced forest in a g…

Paley Shannon-capacity conjecture. There exist constants $a_k,b_k>0$ such that, for every prime $p\equiv1\pmod{k}$,

Quadratic Paley-product conjecture. When $k=2$, the lower bound achieved, $q^{\frac{3}{4}n}$, is optimal.

In the setting of the preceding discussion, let $M$ be the set of integers $m$ satisfying … and let $A_{m,n}$ be the matrix defined in the paper, with $L(n)$ its associated index s…

Let $p$ be a prime with $p\equiv 1\pmod{4}$, and let $q=p^{2s+1}$ for some positive integer $s$. Write $\omega(P_q)$ for the clique number of the Paley graph $P_q$. Improved Paley-…

Let $\{\Phi_n\}$ be the family of Paley equiangular tight frames, with $\Phi_n$ an $m\times n$ matrix and $m=m(n)\in[0.01n,0.99n]$. A matrix family is a restricted isometry for an…

Let $G_p$ be the Paley graph for a prime $p\equiv 1~(\operatorname{mod}4)$, let $\operatorname{LS}(p)$ denote the linear programming bound obtained in the paper, and let…

For primes $p\equiv1\bmod4$, let $\chi$ be the Legendre symbol modulo $p$. Define $\operatorname{PaleyDiscrepancy}[\alpha,\beta]$ to mean that, for every sufficiently large $p$, ……

Let $p$ be a sufficiently large prime, let $\mathbb{F}_p$ be the finite field, and let $R$ be the set of nonzero quadratic residues in $\mathbb{F}_p$. Let $\varepsilon\in(0,1)$ be…