Randomstrasse101 Open Problems (2025) — Conjecture 3

Definitions and mathematical statement

For a prime $p\equiv 1\pmod 4$, the Paley graph $P_p$ has vertex set ${\mathbb{F}}_p$; distinct vertices $x,y$ are adjacent precisely when $x-y$ is a nonzero square in ${\mathbb{F}}_p$. For a finite simple graph $H$, its complement $\overline H$ has the same vertex set and has an edge between distinct vertices precisely when $H$ does not. For a nonempty finite simple graph $H$, its Lovász theta number is \[ \vartheta(H)=\max\left\{\sum_{u,v\in V(H)}X_{uv}: X\in{\mathbb{R}}^{V(H)\times V(H)},\ X=X^{\mathsf T},\ X\succeq0,\ \operatorname{tr}(X)=1,\ X_{uv}=0\ \text{for every }\{u,v\}\in E(H)\right\}. \] For the graph with no vertices, set $\vartheta(H)=0$.

The supplied record denotes by $G_{p,2}$ the "2-localization" of the Paley graph and refers to a description "above." That description is absent from the supplied record. Consequently, the vertex set, adjacency relation, and any choices or additional quantifiers involved in $G_{p,2}$ remain unspecified; the definition of $P_p$ alone does not resolve them.

Conjecture 3, conditional on the missing definition. With $G_{p,2}$ interpreted exactly as in the omitted source description, the proposed assertion is that there exists $p_0\in{\mathbb{N}}$ such that, for every prime $p\ge p_0$ satisfying $p\equiv1\pmod4$, \[ \vartheta\!\left(\overline{G_{p,2}}\right)\le \frac{2}{3}\sqrt p. \] This is an incomplete formulation until the source's definition of 2-localization, including any choices and their quantification, is recovered. The registry labels the problem open; that label is supplied metadata, not an independently verified mathematical or literature assessment.

Short English statement

The proposed bound says that, for every sufficiently large prime $p\equiv1\pmod4$, the complement of the specified 2-localization of the Paley graph has Lovász theta number at most $\frac23\sqrt p$. The supplied record omits the definition of 2-localization, so the graph and any quantification over its defining choices require clarification.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $800855$, exact source problem code catalogue entry; upstream ID $800855$, revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The record attributes the proposal to Bandeira et al., gives proposed year 2026, and labels its status open.
• Bandeira et al., Randomstrasse101: Open Problems of 2025 (2026), Conjecture 3. Supplied source URL: https://arxiv.org/abs/2603.29571. The record reports access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; neither the source nor its access history has been independently verified here. The supplied excerpt refers to an earlier definition of 2-localization that is not included in the record.