betaFeedback

WorksMathematics

New bounds on simplex-avoiding sets in two dimensions

Abstract

We study extremal densities of measurable subsets of metric spaces avoiding prescribed finite geometric configurations. We prove two new upper bounds for three-point avoidance problems: a measurable subset of S2S^2 containing no orthonormal basis has normalized spherical measure at most 7/117/11, and a measurable subset of R2\mathbb{R}^2 containing no unit equilateral triangle has upper Banach density at most 9/169/16. The first bound appears to be the first improvement over the trivial averaging bound for this problem, while the second improves the previously best known upper bound. The proofs are applications of the geometric fractional chromatic number method introduced by Ambrus et al. For this purpose, we formulate the method in a framework that applies both to compact homogeneous spaces and to Euclidean spaces with upper Banach density.

Introduction

We study the maximal density of measurable subsets of geometric spaces avoiding prescribed finite configurations. Following [5], we refer to such extremal quantities as independence densities, generalizing the independence ratio of a graph or hypergraph.

Our first problem concerns subsets of the unit sphere S2\mathbb{S}^{2} containing no orthonormal basis. Let m⊥(S2)m_{\perp}(\mathbb{S}^{2}) denote the supremum of the normalized spherical measures of such sets. The elementary averaging argument gives m⊥(S2)≤2/3m_{\perp}(\mathbb{S}^{2}) \le2/3. We prove the following improvement.

Theorem 1.1. We have

m⊥(S2)≤711≈0.63636.m_{\perp}(\mathbb{S}^{2}) \le\frac{7}{11} \approx0.63636.

The problem has previously been considered in [4, 6, 7, 10], mostly in connection with lower bounds or higher-dimensional variants. To the best of our knowledge, our bound is the first explicitly established improvement over 2/32/3 for this independence-density problem. We could deduce a weaker improvement from the work of Conway and Kochen [8]: their configuration of 40 orthonormal triples implies, by averaging, m⊥(S2)≤79/120≈0.65833m_{\perp}(\mathbb{S}^{2}) \le79/120 \approx0.65833.

Our second problem concerns measurable subsets of R2\mathbb{R}^{2} containing no unit equilateral triangle. Let mΔ(R2)m_{\Delta}(\mathbb{R}^{2}) denote the supremum of their upper Banach densities. A construction of density 1/2 is conjectured to be optimal. The previously best known upper bound was 0.64355, obtained in [6]. We improve it as follows.

Theorem 1.2. We have

mΔ(R2)≤916=0.5625.m_{\Delta}(\mathbb{R}^{2}) \le\frac{9}{16} = 0.5625.

Both of our results are obtained using the geometric fractional chromatic number (GFCN) method, introduced in [15] and subsequently developed in [12, 14, 11]. The method considers random isometric placements of finite point configurations, called probes. The resulting distributions of intersection patterns satisfy linear constraints arising from the forbidden configurations and geometric congruences. Solving the corresponding linear programs yields upper bounds on independence densities.

Our bounds use a 15-point probe in the projective plane and a 14-point probe in the Euclidean plane. The probes were found by computer search, and the bounds are certified by exact rational dual solutions. The supplementary material [13] contains the certificates and an exact-arithmetic verifier.

Section 2 gives an informal overview of the GFCN method. In Sections 3 and 4, we formulate the method for compact homogeneous spaces and Euclidean spaces, respectively. Sections 5 and 6 establish the two bounds above.

The probe method: an informal overview

The geometric fractional chromatic number (GFCN) method was introduced in [15]. Here we describe its probabilistic, probe-based interpretation, introduced in [11]. The basic idea is to study a hypothetical configuration-avoiding set by testing it with randomly placed finite point configurations, which we call probes. Let AA be a Borel set avoiding the forbidden configurations, and let XX be a nonempty finite probe. We place a congruent copy of XX at random and record which points of XX land in AA. This produces a random subset Y⊆XY \subseteq X, or equivalently a probability distribution γA,X\gamma_{A,X} on the subsets of XX. The placement rule is chosen to respect the symmetries of the ambient space. In Euclidean spaces, we initially work with periodic sets; the precise constructions are given in Sections 3 and 4.

There are two sources of constraints on the observation distribution. The first is combinatorial: an observed subset YY cannot contain a forbidden configuration, so γA,X(Y)=0\gamma_{A,X}(Y) = 0 for every such YY. Of course, all observation probabilities are nonnegative and sum to one. These restrictions depend only on which subsets of XX contain forbidden configurations.

The second source is geometric. For any U⊆XU \subseteq X, the probability that all points of UU land in AA, regardless of what happens to the remaining points of XX, is

γ‾A,X(U)=∑Y:U⊆Y⊆XγA,X(Y).\overline{\gamma}_{A,X}(U)=\sum_{Y:U\subseteq Y\subseteq X}\gamma_{A,X}(Y).

If two subsets U,V⊆XU,V\subseteq X are congruent under the relevant group of isometries, their random placements have the same distribution, and therefore

γ‾A,X(U)=γ‾A,X(V).\overline{\gamma}_{A,X}(U)=\overline{\gamma}_{A,X}(V).

These equalities apply to subconfigurations of any size, not just individual points or forbidden configurations. They use geometric information about XX that is not captured by its forbidden-configuration hypergraph. The strength of the method comes from combining these geometric consistency relations with the combinatorial restrictions on the possible observations.

Every point of the probe has the same probability of landing in AA, which equals the density of AA (or its periodic density in the Euclidean setting). We can therefore bound the density by maximizing the common singleton probability γ‾({x0})\overline{\gamma}(\{x_0\}) over all probability distributions on admissible subsets of XX satisfying the congruence equalities. This is a finite linear program. Every avoiding set under consideration yields a feasible observation distribution, so the LP optimum bounds its density.

This density formulation is equivalent to the usual GFCN formulation by a simple change of normalization. In the latter, one assigns nonnegative weights w(Y)w(Y) to admissible subsets, requires ∑Y:x∈Yw(Y)=1\sum_{Y:x\in Y}w(Y)=1 for every x∈Xx\in X, imposes the same congruence relations, and minimizes the total weight ∑Yw(Y)\sum_Y w(Y). If a probability distribution γ\gamma has common singleton marginal p>0p>0, then w(Y)=γ(Y)/pw(Y)=\gamma(Y)/p has total weight 1/p1/p. Conversely, normalizing such weights to have total mass one gives a probability distribution with singleton marginal 1/∑Yw(Y)1/\sum_Y w(Y). Thus the optimum of our density LP is the reciprocal of the corresponding GFCN. If we drop the congruence constraints for subsets of size at least two from the coloring formulation, retaining only the equal singleton marginals, then we recover the ordinary fractional chromatic number of the hypergraph on XX whose edges are the forbidden configurations (see [9]). Thus the additional geometric consistency constraints are precisely what distinguishes GFCN from standard fractional coloring. In this paper, we use the probability normalization because it directly expresses the desired density bound.

The practical challenge is to find probes for which this linear program gives strong bounds. In our applications, we search for such probes computationally and verify the resulting bounds using exact rational certificates. The search procedure is described in Appendix A.

A related use of probabilistic symmetrization appears in the recent proof by OpenAI [22] that the Euclidean plane is not five-colorable. Their proof averages over translations and rotations to construct invariant probability distributions on colorings, followed by a transfer to weak measurable colorings. Their arguments differ substantially from our finite-probe approach, but both methods exploit geometric symmetries through probabilistic averaging.

Probes in compact spaces

Let SS be a compact metric space equipped with a prescribed Borel probability measure δ\delta. Let GG be a compact group acting continuously and transitively on SS by isometries, and assume that δ\delta is GG-invariant. We write μ\mu for normalized Haar measure on GG. The random placement procedure is to choose g∈Gg \in G according to μ\mu, and to send each point x∈Sx \in S to gxgx.

Lemma 3.1. For x∈Sx \in S, let ex:G→Se_x:G \to S be the map ex(g)=gxe_x(g)=gx. The pushforward measure (ex)∗μ(e_x)_*\mu is equal to δ\delta.

Proof. The measure (ex)∗μ(e_x)_*\mu is GG-invariant, since left translation preserves Haar measure. A compact transitive GG-space has a unique GG-invariant Borel probability measure: identify SS with G/GxG/G_x and push Haar measure forward through the quotient map. Since δ\delta is GG-invariant, the two measures are equal. □

Thus the Haar-random placement rule is compatible with the density measure: for every Borel set A⊆SA \subseteq S, δ(A)\delta(A) is the probability that a randomly placed point lands in AA.

Let P\mathcal{P} be a GG-invariant family of nonempty finite subsets of SS. Thus, if P∈PP \in\mathcal{P}, then gP∈PgP \in\mathcal{P} for every g∈Gg \in G. Examples include the pairs of points at distance 11 in a metric space, or the triples forming orthonormal bases on S2S^2. A set A⊆SA \subseteq S is P\mathcal{P}-independent if no member of P\mathcal{P} is contained in AA. We write

mP(S):=sup⁡{δ(A):A⊆S is Borel and P-independent}.m_{\mathcal{P}}(S) := \sup\{\delta(A): A \subseteq S \text{ is Borel and } \mathcal{P}\text{-independent}\}.

For a probe X⊆SX \subseteq S, and for Y⊆XY \subseteq X, define

EA,X(Y):={g∈G:gx∈A⟺x∈Y for every x∈X}E_{A,X}(Y) := \{g \in G : gx \in A \Longleftrightarrow x \in Y \text{ for every } x \in X\}

and

γA,X(Y):=μ(EA,X(Y)).\gamma_{A,X}(Y) := \mu(E_{A,X}(Y)).

This is the probability that a random placement of XX produces exactly the observed pattern YY. For a finite set Z⊆SZ \subseteq S, define

πA(Z):=μ({g∈G:gZ⊆A}).\pi_A(Z) := \mu(\{g \in G : gZ \subseteq A\}).

Since g↦gxg \mapsto gx is continuous, these are probabilities of Borel events whenever AA is Borel.

For Z⊆XZ \subseteq X, define

γ‾A,X(Z):=∑Y:Z⊆Y⊆XγA,X(Y).\overline{\gamma}_{A,X}(Z) := \sum_{Y: Z \subseteq Y \subseteq X} \gamma_{A,X}(Y).

Then

πA(Z)=γ‾A,X(Z)(1)\pi_A(Z) = \overline{\gamma}_{A,X}(Z) \tag*{(1)}

Indeed, the event gZ⊆AgZ \subseteq A is the disjoint union of the events EA,X(Y)E_{A,X}(Y) over all Y⊇ZY \supseteq Z.

Let

IP(X):={Y⊆X:Y is P-independent}.\mathcal{I}_{\mathcal{P}}(X) := \{Y \subseteq X : Y\text{ is }\mathcal{P}\text{-independent}\}.

If AA is P\mathcal{P}-independent, then γA,X(Y)=0\gamma_{A,X}(Y)=0 for every Y∉IP(X)Y \notin\mathcal{I}_{\mathcal{P}}(X), since otherwise a forbidden configuration inside YY would be placed inside AA. Also, if U,V⊆XU,V\subseteq X are congruent, meaning V=hUV=hU for some h∈Gh\in G, then

γ‾A,X(U)=γ‾A,X(V),\overline{\gamma}_{A,X}(U)=\overline{\gamma}_{A,X}(V),

because πA(V)=πA(U)\pi_A(V)=\pi_A(U) by right invariance of Haar measure. Finally, for every x∈Xx\in X,

γ‾A,X({x})=πA({x})=δ(A).\overline{\gamma}_{A,X}(\{x\})=\pi_A(\{x\})=\delta(A).

Definition 3.2. Fix a probe X⊆SX\subseteq S and a point x0∈Xx_0\in X. Let ΓP(X)\Gamma_{\mathcal{P}}(X) be the optimum of the following linear program. The variables are γ(Y)\gamma(Y), Y∈IP(X)Y\in\mathcal{I}_{\mathcal{P}}(X), and

γ‾(Z):=∑Y∈IP(X)Z⊆Yγ(Y).\overline{\gamma}(Z):=\sum_{\substack{Y\in\mathcal{I}_{\mathcal{P}}(X)\\ Z\subseteq Y}}\gamma(Y).

Maximize γ‾({x0})\overline{\gamma}(\{x_0\}), subject to

γ(Y)≥0,∑Y∈IP(X)γ(Y)=1,\gamma(Y)\geq0,\qquad\sum_{Y\in\mathcal{I}_{\mathcal{P}}(X)}\gamma(Y)=1,

and

γ‾(U)=γ‾(V)whenever U,V⊆X are congruent.\overline{\gamma}(U)=\overline{\gamma}(V)\qquad\text{whenever }U,V\subseteq X\text{ are congruent}.

Since all singleton subsets of XX are congruent, the optimum does not depend on the choice of x0x_0.

Theorem 3.3. For every probe X⊆SX\subseteq S,

mP(S)≤ΓP(X).m_{\mathcal{P}}(S)\leq\Gamma_{\mathcal{P}}(X).

Proof. Every Borel P\mathcal{P}-independent set AA gives a feasible point γA,X\gamma_{A,X} of the linear program above. Its objective value is

γ‾A,X({x0})=δ(A).\overline{\gamma}_{A,X}(\{x_0\})=\delta(A).

Taking the supremum over AA proves the theorem. □\square

Remark 3.4. If one wants to take the supremum over all δ\delta-measurable independent sets instead of Borel ones, the value is unchanged. Indeed, δ\delta is a regular Borel probability measure on the compact metric space SS, and every measurable independent set contains compact independent subsets of arbitrarily close measure.

Probes in Euclidean spaces

We next record the corresponding form of the method for Euclidean spaces. Let E(n)=O(n)⋉RnE(n) = O(n) \ltimes\mathbb{R}^{n} be the Euclidean isometry group, and let P\mathcal{P} be an E(n)E(n)-invariant family of nonempty finite subsets of Rn\mathbb{R}^{n}. Thus, if P∈PP \in\mathcal{P}, then RP+v∈PRP + v \in\mathcal{P} for every R∈O(n)R \in O(n) and v∈Rnv \in\mathbb{R}^{n}. A measurable set A⊆RnA \subseteq\mathbb{R}^{n} is P\mathcal{P}-independent if no member of P\mathcal{P} is contained in AA.

For a measurable A⊆RnA \subseteq\mathbb{R}^{n}, define its upper Banach density by

d‾(A):=lim sup⁡T→∞sup⁡u∈Rnλn(A∩(u+[0,T]n))Tn.\overline{d}(A) := \limsup_{T \to\infty} \sup_{u \in\mathbb{R}^{n}} \frac{\lambda_{n}\left(A \cap\left(u + [0,T]^{n}\right)\right)}{T^{n}}.

where λn\lambda_{n} denotes nn-dimensional Lebesgue measure. We write

mP(Rn):=sup⁡{d‾(A):A⊆Rn is Lebesgue measurablem_{\mathcal{P}}(\mathbb{R}^{n}) := \sup\{\overline{d}(A) : A \subseteq\mathbb{R}^{n}\text{ is Lebesgue measurable}
and A is P-independent}.\text{and } A\text{ is }\mathcal{P}\text{-independent}\}.

First consider periodic independent sets. Let L⊆RnL \subseteq\mathbb{R}^{n} be a full-rank lattice, let

TL:=Rn/L,\mathbb{T}_{L} := \mathbb{R}^{n}/L,

and let qL:Rn→TLq_{L} : \mathbb{R}^{n} \to\mathbb{T}_{L} be the quotient map. If A=qL−1(AL)A = q_{L}^{-1}(A_{L}), where AL⊆TLA_{L} \subseteq\mathbb{T}_{L} is Borel, its periodic density is

δL(A):=mL(AL),\delta_{L}(A) := m_{L}(A_{L}),

where mLm_{L} is normalized Haar measure on TL\mathbb{T}_{L}.

The random placement procedure for an LL-periodic set is to choose

(R,t)∈O(n)×TL(R,t) \in O(n) \times\mathbb{T}_{L}

according to product Haar measure and to place x∈Rnx \in\mathbb{R}^{n} at

ϕR,t(x):=qL(Rx)+t∈TL.\phi_{R,t}(x) := q_{L}(Rx) + t \in\mathbb{T}_{L}.

For a probe X⊆RnX \subseteq\mathbb{R}^{n}, Y⊆XY \subseteq X, and a periodic Borel set A=qL−1(AL)A = q_{L}^{-1}(A_{L}), define

γA,X(Y):=Pr⁡(ϕR,t(x)∈AL⟺x∈Y for every x∈X).\gamma_{A,X}(Y) := \Pr\bigl(\phi_{R,t}(x) \in A_{L} \Longleftrightarrow x \in Y\text{ for every }x \in X\bigr).

For a finite set Z⊆RnZ \subseteq\mathbb{R}^{n}, define

πA(Z):=Pr⁡(ϕR,t(z)∈AL for every z∈Z).\pi_{A}(Z) := \Pr\bigl(\phi_{R,t}(z) \in A_{L}\text{ for every }z \in Z\bigr).

These are probabilities of Borel events, since (R,t)↦qL(Rx)+t(R,t) \mapsto q_{L}(Rx) + t is continuous.

For Z⊆XZ \subseteq X, define γ‾A,X(Z)\overline{\gamma}_{A,X}(Z) by the same sum as in § 3. As before, πA(Z)=γ‾A,X(Z)\pi_{A}(Z) = \overline{\gamma}_{A,X}(Z), since the event that all points of ZZ land in ALA_{L} is the disjoint union of the exact observations containing ZZ.

If AA is P\mathcal{P}-independent, then γA,X(Y)=0\gamma_{A,X}(Y) = 0 whenever Y∉IP(X)Y \notin I_{\mathcal{P}}(X), because any placement observing YY would lift a forbidden configuration P⊆YP \subseteq Y to RP+t~⊆ARP + \widetilde{t} \subseteq A for a lift t~\widetilde{t} of tt.

If U,V⊆XU,V \subseteq X are Euclidean-congruent, then

πA(U)=πA(V).\pi_{A}(U) = \pi_{A}(V).

Indeed, if V=R0U+vV=R_0U+v, then the change of variables (R,t)↦(RR0,t+qL(Rv))(R,t)\mapsto(RR_0,t+q_L(Rv)) preserves product Haar measure on O(n)×TLO(n)\times\mathbb{T}_L. Finally,

πA({x})=δL(A)\pi_A(\{x\})=\delta_L(A)

for every x∈Rnx\in\mathbb{R}^n, because qL(Rx)+tq_L(Rx)+t is uniformly distributed on TL\mathbb{T}_L for every fixed RR.

For a Euclidean probe X⊆RnX\subseteq\mathbb{R}^n and x0∈Xx_0\in X, define ΓP(X)\Gamma_{\mathcal P}(X) by the linear program in § 3, with congruence interpreted as Euclidean congruence. The preceding arguments show that γA,X\gamma_{A,X} satisfies its constraints whenever AA is an LL-periodic P\mathcal P-independent set.

Proposition 4.1. If A=qL−1(AL)⊆RnA=q_L^{-1}(A_L)\subseteq\mathbb{R}^n, with AL⊆TLA_L\subseteq\mathbb{T}_L Borel, is LL-periodic and P\mathcal P-independent, then

δL(A)≤ΓP(X)\delta_L(A)\leq\Gamma_{\mathcal P}(X)

for every probe X⊆RnX\subseteq\mathbb{R}^n.

Proof. The actual observation probabilities γA,X\gamma_{A,X} form a feasible point of the linear program defining ΓP(X)\Gamma_{\mathcal P}(X), and the objective value is

γ‾A,X({x0})=πA({x0})=δL(A).\overline{\gamma}_{A,X}(\{x_0\})=\pi_A(\{x_0\})=\delta_L(A).

The following lemma gives a periodic approximation when the forbidden configurations have uniformly bounded diameter.

Write DP:=sup⁡P∈Pdiam⁡(P)D_{\mathcal P}:=\sup_{P\in\mathcal P}\operatorname{diam}(P), with DP=0D_{\mathcal P}=0 when P=∅\mathcal P=\varnothing.

Lemma 4.2. Assume DP<∞D_{\mathcal P}<\infty. Let A⊆RnA\subseteq\mathbb{R}^n be Lebesgue measurable and P\mathcal P-independent. For every ε>0\varepsilon>0, there are a full-rank lattice LL and an LL-periodic Borel P\mathcal P-independent set B⊆RnB\subseteq\mathbb{R}^n such that

δL(B)≥d‾(A)−ε.\delta_L(B)\geq\overline{d}(A)-\varepsilon.

Proof. Choose ρ>DP/2\rho>D_{\mathcal P}/2. Since the boundary-strip proportion tends to zero as T→∞T\to\infty, the definition of d‾(A)\overline{d}(A) lets us choose T>2ρT>2\rho and u∈Rnu\in\mathbb{R}^n such that

λn(A∩(u+[0,T]n))Tn≥d‾(A)−ε3\frac{\lambda_n(A\cap(u+[0,T]^n))}{T^n}\geq\overline{d}(A)-\frac{\varepsilon}{3}

and such that the boundary strip

(u+[0,T]n)∖(u+[ρ,T−ρ]n)(u+[0,T]^n)\setminus(u+[\rho,T-\rho]^n)

has measure at most εTn/3\varepsilon T^n/3. By inner regularity, choose a compact set

K⊆A∩(u+[ρ,T−ρ]n)K\subseteq A\cap(u+[\rho,T-\rho]^n)

with

λn(K)≥λn(A∩(u+[ρ,T−ρ]n))−εTn3.\lambda_n(K)\geq\lambda_n(A\cap(u+[\rho,T-\rho]^n))-\frac{\varepsilon T^n}{3}.

Let L=TZnL=T\mathbb{Z}^n, and set

B:=K+L.B:=K+L.

Then BB is LL-periodic and Borel. Distinct translates K+ℓK+\ell, ℓ∈L\ell\in L, are separated by distance at least 2ρ>DP2\rho>D_{\mathcal{P}}. Hence any member of P\mathcal{P} contained in BB would have to lie in a single translate of KK. Translating it back would give a member of P\mathcal{P} contained in K⊆AK\subseteq A, contradicting the P\mathcal{P}-independence of AA.

The quotient map qLq_L is injective on KK, and qL(K)q_L(K) is compact in TL\mathbb{T}_L. Therefore B=qL−1(qL(K))B=q_L^{-1}(q_L(K)) and

δL(B)=mL(qL(K))=λn(K)Tn≥d‾(A)−ε.\delta_L(B)=m_L(q_L(K))=\frac{\lambda_n(K)}{T^n}\ge\overline{d}(A)-\varepsilon.

Theorem 4.3. Assume DP<∞D_{\mathcal{P}}<\infty. Then, for every probe X⊆RnX\subseteq\mathbb{R}^n,

mP(Rn)≤ΓP(X).m_{\mathcal{P}}(\mathbb{R}^n)\le\Gamma_{\mathcal{P}}(X).

Proof. Apply Lemma 4.2 to a measurable P\mathcal{P}-independent set AA, then apply Proposition 4.1 to the resulting periodic set, and let ε→0\varepsilon\to0. □

Orthonormal basis-avoiding sets on the sphere

In this section we apply the GFCN machinery to prove Theorem 1.1, which states that m⊥(S2)≤7/11m_{\perp}(S^2)\le7/11.

The problem of avoiding orthonormal bases is closely tied to the Kochen–Specker theorem. The theorem states that there is no assignment of values 0 and 1 to all points of S2S^2 such that antipodal points receive the same value and every orthonormal basis of R3\mathbb{R}^3 has exactly one vector assigned 1 [1]. The condition on orthonormal bases is equivalent to requiring that no two orthogonal points both receive 1 and that no orthonormal basis consists entirely of points receiving 0. Our problem retains only the latter restriction, requiring the measurable set under consideration to contain no orthonormal basis without requiring its complement to avoid orthogonal pairs.

Let σ\sigma denote normalized spherical measure. If A⊆S2A\subseteq S^2 contains no orthonormal basis, then at most two vectors of any orthonormal basis lie in AA. Averaging over uniformly random orthonormal bases, each vector lies in AA with probability σ(A)\sigma(A), so 3σ(A)≤23\sigma(A)\le2. Therefore

m⊥(S2)≤23.(2)m_{\perp}(S^2)\le\frac{2}{3}. \tag*{(2)}

For lower bounds, it is useful to consider the classical problem of avoiding orthogonal pairs. Witsenhausen asked for the largest measurable subset of Sn−1S^{n-1} containing no orthogonal pair, and the expected extremal example is the double cap: two antipodal open spherical caps of angular radius π/4\pi/4 [2, 3]. On S2S^2 a double cap has measure 1−1/2≈0.29291-1/\sqrt{2}\approx0.2929. The best known upper bound for Witsenhausen’s problem is 0.2953, obtained in [11]. Since a single double cap contains no orthogonal pair, the union of two double caps with orthogonal axes contains no orthogonal triple; this already gives

m⊥(S2)≥2(1−12)=2−2≈0.5858.m_{\perp}(S^2) \ge2\left(1-\frac{1}{\sqrt{2}}\right)=2-\sqrt{2}\approx0.5858.

Recently, Williams and Constantin [10] improved this lower bound by constructing a curved “scalloped belt” N0⊂S2N_0 \subset S^2 with no three mutually orthogonal directions and measure

σ(N0)=1−12+2log⁡2π≈0.6049.\sigma(N_0)=1-\frac{1}{\sqrt{2}}+\frac{\sqrt{2}\log2}{\pi}\approx0.6049.

Their construction supersedes earlier improvements by Perez [4]. They conjecture it to be optimal. This construction arose from the study of subsets of S2S^2 admitting assignments of 0 and 1 that agree at antipodal points, assign 1 to no orthogonal pair, and assign exactly one 1 to every orthonormal basis contained in the subset. The set N0N_0 is disjoint from the double cap centered at the north and south poles, and their union admits such an assignment, with value 0 on N0N_0 and value 1 on the double cap.

Since changing the signs of the vectors in an orthonormal basis independently preserves orthonormality, the set A∪(−A)A \cup(-A) is basis-avoiding whenever A⊆S2A \subseteq S^2 is, and σ(A∪(−A))≥σ(A)\sigma(A \cup(-A)) \ge\sigma(A). We may therefore restrict to antipodally symmetric sets and pass to the projective plane by identifying antipodal points on the sphere. Let π:S2→RP2\pi:S^2 \to\mathbb{R}P^2 be the antipodal quotient, and endow RP2\mathbb{R}P^2 with the quotient round metric and the probability measure σˉ:=π∗σ\bar{\sigma}:=\pi_*\sigma. Let P⊥\mathcal{P}_{\perp} be the family of projective orthonormal triples

{π(u1),π(u2),π(u3)},\{\pi(u_1),\pi(u_2),\pi(u_3)\},

where (u1,u2,u3)(u_1,u_2,u_3) ranges over orthonormal bases of R3\mathbb{R}^3. For a probe X⊆RP2X \subseteq\mathbb{R}P^2, write Γ⊥(X):=ΓP⊥(X)\Gamma_{\perp}(X):=\Gamma_{\mathcal{P}_{\perp}}(X).

Lemma 5.1. We have

m⊥(S2)=mP⊥(RP2).m_{\perp}(S^2)=m_{\mathcal{P}_{\perp}}(\mathbb{R}P^2).

Proof. Let A⊆S2A \subseteq S^2 be measurable and contain no orthonormal basis. For every ε>0\varepsilon>0, choose a compact set K⊆AK \subseteq A with σ(K)≥σ(A)−ε\sigma(K)\ge\sigma(A)-\varepsilon. The set B:=π(K)B:=\pi(K) is compact and P⊥\mathcal{P}_{\perp}-independent, since a projective orthonormal triple in BB would lift to an orthonormal basis contained in KK. As π−1(B)=K∪(−K)\pi^{-1}(B)=K\cup(-K), we have

σˉ(B)=σ(K∪(−K))≥σ(A)−ε.\bar{\sigma}(B)=\sigma(K\cup(-K))\ge\sigma(A)-\varepsilon.

Taking the supremum over AA and letting ε→0\varepsilon\to0 gives m⊥(S2)≤mP⊥(RP2)m_{\perp}(S^2)\le m_{\mathcal{P}_{\perp}}(\mathbb{R}P^2). Conversely, if B⊆RP2B\subseteq\mathbb{R}P^2 is Borel and P⊥\mathcal{P}_{\perp}-independent, then π−1(B)\pi^{-1}(B) is Borel, contains no orthonormal basis, and satisfies σ(π−1(B))=σˉ(B)\sigma(\pi^{-1}(B))=\bar{\sigma}(B). This gives the reverse inequality. □

The space RP2\mathbb{R}P^2 is compact, and the natural action of O(3)O(3) is continuous, transitive, and isometric. Both σˉ\bar{\sigma} and P⊥\mathcal{P}_{\perp} are O(3)O(3)-invariant. Thus Theorem 3.3 applies to projective probes. Their random placement is obtained by applying a Haar-uniform element of O(3)O(3) to all the projective points. Here two projective subconfigurations are congruent precisely when a single element of O(3)O(3) maps one onto the other.

We now present a fifteen-point probe X15⊆RP2X_{15} \subseteq\mathbb{R}P^2. The fifteen points of X15X_{15} are represented by the nonzero integer vectors (xj,yj,zj)(x_j,y_j,z_j) listed in Table 1. Figure 1 shows the corresponding unit representatives chosen in the closed northern hemisphere. The left panel gives an oblique view of the hemisphere, while the right panel shows its orthogonal projection onto the plane z=0z=0. Quarter great-circle arcs indicate orthogonal pairs among the chosen representatives. The labels in both panels match the row order of Table 1.

Oblique and top views of the fifteen-point projective probe $X_{15}$

Figure 1. The fifteen-point projective probe X15X_{15}, represented by unit vectors in the closed northern hemisphere of S2S^2. Both panels show the same labeled representatives and quarter great-circle arcs joining orthogonal pairs.

For this probe, the finite linear program gives Γ⊥(X15)=7/11\Gamma_{\perp}(X_{15})=7/11. Combining Lemma 5.1 and Theorem 3.3, we obtain

m⊥(S2)=mP⊥(RP2)≤Γ⊥(X15)=711,m_{\perp}(S^2)=m_{P\perp}(\mathbb{R}P^2)\leq\Gamma_{\perp}(X_{15})=\frac{7}{11},

as asserted in Theorem 1.1.

Unit equilateral triangles in the plane

The seminal paper by Erdős et al. [17], which introduced Euclidean Ramsey theory, begins with a simple illustrative example:

We are concerned in this paper with problems of the type illustrated as follows: Is it true that for any partition of the Euclidean plane into two classes (we say that the plane is

jjxjx_jyjy_jzjz_j
1−2-2−1-11
2−1-1−1-11
3−1-111
4−1-121
50−1-11
6001
7011
8010
91−2-20
101−1-11
11111
12101
13211
14210
15100

caption: Table 1. Integer vectors representing the projective points of X15X_{15}. The indices match the labels in Figure 1.

:::

two-colored), there exists a set of three points all in the same class forming the vertices of an equilateral triangle of side length 1? (We call such a set monochromatic.)

In this example the answer is “no,” as can be seen by dividing the points (x,y)(x,y) into two classes according to the parity of [2y/3][2y/\sqrt{3}].

The two color classes in this construction both avoid unit equilateral triangles and have upper Banach density 1/21/2. A different family of “zebra-stripe” constructions was given by Jelínek et al. [19], achieving the same density. In contrast, Currier, Moore, and Yip [21] showed that every two-coloring of the plane contains a monochromatic congruent copy of any prescribed three-term arithmetic progression.

Let Δ⊆R2\Delta\subseteq\mathbb{R}^{2} be the vertex set of a unit equilateral triangle, and let

PΔ:={RΔ+v:R∈O(2), v∈R2}.\mathcal{P}_{\Delta}:=\{R\Delta+v:R\in O(2),\ v\in\mathbb{R}^{2}\}.

We write

mΔ(R2):=mPΔ(R2)andΓΔ(X):=ΓPΔ(X).m_{\Delta}(\mathbb{R}^{2}):=m_{\mathcal{P}_{\Delta}}(\mathbb{R}^{2}) \qquad\text{and} \qquad\Gamma_{\Delta}(X):=\Gamma_{\mathcal{P}_{\Delta}}(X).

Thus mΔ(R2)≥1/2m_{\Delta}(\mathbb{R}^{2})\geq1/2. Although the independence density problem imposes no restriction on the complement of a PΔ\mathcal{P}_{\Delta}-independent set, no such set with upper Banach density greater than 1/21/2 is known to us. We conjecture that mΔ(R2)=1/2m_{\Delta}(\mathbb{R}^{2})=1/2.

To describe the two probes used below, we identify R2\mathbb{R}^{2} with the complex plane and set ω=(1+i3)/2\omega=(1+i\sqrt{3})/2 and η=(5+i11)/6\eta=(5+i\sqrt{11})/6.

We first establish an elementary upper bound using a variation of the construction of Leo and William Moser [16].

Theorem 6.1. mΔ(R2)≤5/8m_\Delta(\mathbb{R}^2) \leq5/8.

Proof. Adding one vertex to the Moser spindle gives the eight-vertex unit-distance graph M′M' shown in Figure 2.

Figure 2. The eight-point probe X8X_8 and its unit-distance graph M′M', obtained by adding vertex 8 to the Moser spindle.

It is easy to verify that any six vertices of M′M' induce a subgraph containing a triangle. By Lemma 4.2, it suffices to prove the bound for LL-periodic Borel triangle-free sets AA. By this property of M′M', every placement of X8X_8 in the plane has at most five vertices in AA. By linearity of expectation, this implies that δL(A)≤5/8\delta_L(A) \leq5/8.

The 5/85/8 bound uses only that every triangle-free subset of X8X_8 has at most five points and that each point of X8X_8 has the same inclusion probability under a random placement. The GFCN linear program also imposes congruence constraints for subconfigurations containing more than one point. We apply these additional constraints to a fourteen-point probe X14={z1,…,z14}X_{14} = \{z_1, \ldots, z_{14}\}.

For j=1,…,14j = 1, \ldots, 14, let zj=aj+bjω+cjη+djωηz_j = a_j + b_j\omega+ c_j\eta+ d_j\omega\eta, using ω\omega and η\eta as above. Figure 3 depicts this probe, and Table 2 lists the integer coefficients aj,bj,cj,dja_j, b_j, c_j, d_j.

Figure 3. The fourteen-point planar probe X14X_{14}, with edges joining pairs of points at unit distance.

jjaja_jbjb_jcjc_jdjd_j
13310
22410
30340
40440
52221
61321
72321
83321
91421
104102
111132
123013
133113
142213

Table 2. Integer coefficients specifying the points of X14X_{14}. The indices match the labels in Figure 3.

Proof of Theorem 1.2. Every member of PΔ\mathcal{P}_\Delta has diameter 1. Theorem 4.3 then gives mΔ(R2)≤ΓΔ(X14)m_\Delta(\mathbb{R}^2) \leq\Gamma_\Delta(X_{14}). The linear program gives ΓΔ(X14)=9/16\Gamma_\Delta(X_{14}) = 9/16.

Open Problems

Several natural questions remain open concerning both extremal densities and the effectiveness of the GFCN method itself.

The most immediate question is whether the density 1/21/2 construction described in § 6 is optimal. For unit equilateral triangle avoidance, our upper bound of 9/169/16 is still above the conjectured optimal value of 1/21/2.

Curiously, we were unable to obtain a better upper bound even under the stronger assumption that both a measurable set AA and its complement R2∖A\mathbb{R}^{2}\setminus A avoid unit equilateral triangles.

The corresponding problem on the sphere also remains open. Williams and Constantin [10] conjectured that their scalloped-belt construction is optimal, which would give

m⊥(S2)=1−12+2log⁡2π≈0.6049.m_{\perp}(S^{2}) = 1 - \frac{1}{\sqrt{2}} + \frac{\sqrt{2}\log2}{\pi} \approx0.6049.

We establish the upper bound 7/11≈0.63647/11 \approx0.6364. Closing this gap is a natural direction for further work.

A more general question concerns the effectiveness of the GFCN method itself. For a family P\mathcal{P} of forbidden configurations in a space SS, Theorems 3.3 and 4.3 establish, under their respective assumptions, that

mP(S)≤inf⁡X⊂S finite, nonemptyΓP(X).m_{\mathcal{P}}(S) \le\inf_{\substack{X \subset S\ \text{finite, nonempty}}} \Gamma_{\mathcal{P}}(X).

For which spaces and forbidden families does equality hold? Equivalently, can the optimal independence density always be approximated arbitrarily closely by bounds obtained from finite probes? For unit-distance avoidance in the plane, the results of [18] and [20] imply equality, since the LP bound for every finite probe is at most its independence ratio. The question remains open in most other cases.

Use of generative AI tools. Generative AI tools, including GPT-6 and Claude Fable 5.2, were used to assist with writing the computer code, drafting the supplementary documentation, and improving the exposition and organization of the manuscript. All AI-assisted material was reviewed by the authors, who take full responsibility for the mathematical results, computational verification, and final content of the paper.

Acknowledgements

D. C., Á. D., D. V., and P. Zs. were supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory (RRF-2.3.1-21-2022-00004). Á. D. and D. V. were supported by the grant NKFIH-153165. D. C. and P. M. were supported by the grant NKFIH-154121. We thank András Szabó for his help in preparing the supplementary material, and Gergely Ambrus, Máté Matolcsi, and Kenneth Moore for helpful discussions and valuable insights.

Appendix A. Computational search for the probes

The probes X14X_{14} and X15X_{15} were obtained by computer-assisted searches over finite geometric configurations, following the general approach of [15, 12, 11]. The search software generates candidate configurations by geometric extensions and ranks them using numerical solutions of their GFCN linear programs. Both beam search and Monte Carlo tree search are implemented for exploring the resulting space of configurations.

For the planar problem, points are represented by integer quadruples (a,b,c,d)(a,b,c,d) encoding a+bω+cη+dωηa+b\omega+c\eta+d\omega\eta, where ω\omega and η\eta are defined in § 6. Candidate extensions include adjoining points at unit distance from existing points, completing equilateral triangles, and completing parallelograms. Configurations are canonicalized under translations and symmetries of the Moser lattice to avoid duplicate candidates. The fourteen integer quadruples for the resulting probe X14X_{14} are listed in Table 2.

For the spherical problem, the search works with projective directions, identifying a unit vector uu with −u-u. The extension operation takes two nonparallel representatives u,vu,v and adjoins the projective direction represented by u×vu \times v, which is orthogonal to both. The same cross-product extension rule is used in the spherical search described in [11]. The exact coordinates of X15X_{15} are listed in Table 1.

For each candidate XX, its graph has edges between pairs at unit distance in the planar problem or between orthogonal pairs in the spherical problem. The triangle-free vertex subsets are precisely the admissible observation patterns, and the linear program also imposes the congruence constraints of § 3 and § 4. The search evaluates the LP numerically, using a smaller value of ΓΔ(X)\Gamma_{\Delta}(X) or Γ⊥(X)\Gamma_{\perp}(X) as a better score. For the final probes, X14X_{14} has 23 unit-distance pairs and 6 unit equilateral triangles, while X15X_{15} has 25 orthogonal pairs and 6 orthonormal triples. These counts can be checked directly from the exact coordinates, whereas the LP congruence constraints also use geometric information not contained in the graphs. The exact LP values ΓΔ(X14)=9/16\Gamma_{\Delta}(X_{14}) = 9/16 and Γ⊥(X15)=7/11\Gamma_{\perp}(X_{15}) = 7/11 are verified by rational primal and dual certificates independently of the numerical search.

Domonkos Czifra, HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053 Budapest, Hungary Email address: [email protected]

Ákos Dúcz, HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053 Budapest, Hungary Email address: [email protected]

Péter Madarasi, HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053 Budapest, Hungary; and Department of Operations Research, ELTE Eötvös Loránd University, Pázmány P. s. 1/C, 1117 Budapest, Hungary Email address: [email protected]

Dániel Varga, HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053 Budapest, Hungary Email address: [email protected]

Pál Zsámboki, HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053 Budapest, Hungary Email address: [email protected]

References

  1. [1]S. Kochen and E. P. Specker, The problem of hidden variables in quantum mechanics, J. Math. Mech. 17 (1967), 59–87.
  2. [2]H. S. Witsenhausen, Spherical sets without orthogonal point pairs, Amer. Math. Monthly 81 (1974), no. 10, 1101–1102.DOI
  3. [3]G. Kalai, Some old and new problems in combinatorial geometry I: around Borsuk’s problem, in Surveys in Combinatorics 2015, London Math. Soc. Lecture Note Ser. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 147–174.arxiv.org/abs/1505.04952
  4. [4]A.-M. Perez, On generalizations of the double cap conjecture, Research Science Institute report, 2019.
  5. [5]D. Castro-Silva, Geometrical sets with forbidden configurations, Forum Math. Sigma 11 (2023), e44.
  6. [6]D. Castro-Silva, F. M. de Oliveira Filho, L. Slot, and F. Vallentin, A recursive Lovász theta number for simplex-avoiding sets, Proc. Amer. Math. Soc. 150 (2022), no. 8, 3307–3322.
  7. [7]D. Zakharov, Spherical sets avoiding orthonormal bases, C. R. Math. 363 (2025), 1351–1362.arxiv.org/abs/2310.06821
  8. [8]J. H. Conway and S. Kochen, The free will theorem, Foundations of Physics 36 (2006), 1441–1473.DOI
  9. [9]E. R. Scheinerman and D. H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs, Wiley, New York, 1997.
  10. [10]T. Williams and A. Constantin, Maximal non-Kochen-Specker sets and a lower bound on the size of Kochen-Specker sets, Phys. Rev. A 111 (2025), no. 1, 012223.DOI
  11. [11]D. Czifra, Á. Dúcz, M. Matolcsi, D. Varga, and P. Zsámboki, Improved bounds for the double cap conjecture, preprint, https://arxiv.org/abs/2605.28709.
  12. [12]M. Matolcsi, I. Z. Ruzsa, D. Varga, and P. Zsámboki, The fractional chromatic number of the plane is at least 4, preprint, https://arxiv.org/abs/2311.10069.
  13. [13]Supplementary material for this paper (verification code and data). Available at https://users.renyi.hu/~akos/triangles/triangle_reproduction/site/.
  14. [14]V. F. Lev, M. Matolcsi, P. P. Pach, and D. Varga, On the density of Kravitz sets, preprint, https://arxiv.org/abs/2510.16522.
  15. [15]G. Ambrus, A. Csizsárik, M. Matolcsi, D. Varga, and P. Zsámboki, The density of planar sets avoiding unit distances, Math. Program. 207 (2024), 303–327.DOI
  16. [16]L. Moser and W. Moser, Solution to problem 10, Canad. Math. Bull. 4 (1961), 187–189.
  17. [17]P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus, Euclidean Ramsey theorems. I, Journal of Combinatorial Theory, Series A 14 (1973), no. 3, 341–363.DOI
  18. [18]S. Li and Y. Su, Every n points in the plane contain (m₁ + o(1))n points with no unit distance, preprint, arXiv:2610.15424 (2026).arxiv.org/abs/2610.15424
  19. [19]V. Jelínek, J. Kynčl, R. Stolař, and T. Valla, Monochromatic triangles in two-colored plane, Combinatorica 29 (2009), 699–718.DOI
  20. [20]Á. Dúcz, Measurable Independence Density Equals the Finite Independence-Ratio Infimum in the Euclidean Plane, Hexagon preprint, hexagon:2610.00171v1 (2026). https://hexagonmath.org/2610.00171v1.
  21. [21]G. Currier, K. Moore, and C. H. Yip, Any two-coloring of the plane contains monochromatic 3-term arithmetic progressions, Combinatorica 44 (2024), 1367–1380.DOI
  22. [22]OpenAI, The Euclidean plane is not five-colorable, OpenAI Math Release preprint (2026). https://github.com/openai/math/blob/main/preprints/The-Euclidean-plane-is-not-five-colorable-September-23-2026/paper.pdf.

Paper details

vlnc:W_ezdhvve9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents