Universal vertices and effective dimension in geometric-graph entropy

Summary

The question. Scatter $n$ points at random in a region, and join two of them whenever they are within a fixed distance $r$ of each other. Networks like this, called random geometric graphs, model wireless sensor networks, contact networks and spatial infrastructure. How many bits does it take, on average, to store one? That number is the Shannon entropy of the graph. It is also the best possible size of a lossless compressed file for it, to within one bit.

The rough answer, and when it fails. Each point has $d$ coordinates. The other $n-1$ points pin each coordinate down to about $1/n$, which costs about $\log_2 n$ bits. So a first guess is $d\,n\log_2 n$ bits in total. That guess fails in two ways:

• Universal points cost nothing. A point that lies within distance $r$ of every possible position is joined to every other point, wherever they fall. Its links reveal nothing about where it is.
• Blind directions cost nothing. A connection rule can be blind to some directions. Then the links say nothing about the coordinates in those directions.

What was found. The leading cost is exactly the effective dimension times $n\log_2 n$. The effective dimension is the average number of coordinates that a point's links actually reveal. On any convex region it is $d$ times the fraction of points that are not universal. The error is at most a constant times $n$.

A concrete example. In the unit square with $r=1$, the universal points form the lens-shaped region shown in the banner. It contains about 31.5% of all points. The true cost is about $1.370\,n\log_2 n$ bits. In 2026, Vippathalla, Coon and Badiu conjectured that it was about $1.461\,n\log_2 n$, an overestimate of 6.25%. Their estimate used a smaller central disc as the region of points that cost nothing.

What this refutes and what it confirms.

The source's upper bounds remain valid. Only their claimed sharpness fails.

How sure we are. Every theorem has a complete written proof. The computer checks are sanity checks of constants, not proofs. This is an anonymous, AI-assisted, unrefereed candidate. Its review was internal and AI-assisted, not peer review.

Summary for specialists

Let $X_1,\dots,X_n$ be independent with a density $m\le f\le M$ on a domain $D$. The labelled hard graph $G_n$ joins $i\ne j$ when $\lVert X_i-X_j\rVert\le r$, with $r$ fixed as $n\to\infty$, and $H$ denotes Shannon entropy in bits. Put $U_r=\{x\in D: D\subseteq \overline B(x,r)\}$ and $u_r=\mu(U_r)$.

All statements about the conjecture refer to arXiv:2601.10778v1, the version inspected. Its abstract says: "we conjecture that the entropy behaves asymptotically as the leading order terms of our derived upper bounds". In that source, $\beta(r)$ is the volume of the central ball of radius $r-\sqrt d/2$ intersected with the cube.

Technical account

Upper bounds by counting. Flag the universal vertices, which costs at most $n$ bits. Every edge at a flagged vertex is present. For the remaining $N$ vertices, Warren's sign-pattern theorem bounds the number of possible distance-threshold graphs on $t$ points in $\mathbb R^d$ by $2^{dt\log_2 t+O(t)}$ (Lemma 2.1). Taking expectations gives $d(1-u_r)\,n\log_2 n+(1+C_d)n$.

Lower bounds by collisions. When a new vertex arrives, its adjacency word to the earlier $k$ vertices identifies its position to within about $1/k$ in each direction that the rule can see. Lemma 2.2 turns this into an entropy bound through the disagreement distance $\Delta_\mu(x,y)=\mu(A_x\triangle A_y)$, which is the $L^1$ neighbourhood metric of the graphon. On convex domains the new ingredient is a quantitative separation estimate (Lemma 3.2):

where $\delta$ is the distance to $\partial D$ and $s(x)=R(x)-r$ is the slack to universality. The constant degenerates near $\partial D$ and near $U_r$, but only its logarithm is integrated, and Lemma 3.3 shows that this integral is finite. The argument sweeps a thin spherical shell near the part of the ball's boundary that lies inside $D$.

Why the cube conjecture fails. For the cube, $U_r$ is the set of points whose farthest corner is within distance $r$. The source's coefficient uses only a central ball inside it. A perturbation argument using strict Cauchy–Schwarz shows that $U_r$ is strictly larger throughout $\sqrt d/2<r<\sqrt d$. In the square at $r=1$, $u_2(1)=1+\pi/3-\sqrt3\approx0.315$, against the central disc's area $\pi(1-1/\sqrt2)^2\approx0.270$.

Fourier rank on the torus. A translation rule $b$ can be blind to some directions. The lattice generated by its nonzero Fourier frequencies has rank $k$, and the latent positions factor through a $k$-dimensional torus. The lower bound uses $k$ real-linearly independent frequencies. The upper bound quantises the factored positions on a generic grid of open cubes and applies relative isoperimetry (Lemma 5.2), which gives a linear remainder. For the ball rule, every coordinate frequency $e_j$ has a nonzero Fourier coefficient at every $0<r<\sqrt d/2$ (Lemma 5.5), so $k=d$.

What is classical and what is new. Warren's bound, the graphon neighbourhood metric, collision lower bounds, relative isoperimetry and the idea of conditioning on universal vertices (which the source applies to a smaller region) are established tools, and the paper cites them. The bounded literature search found no earlier statement of the coefficient theorems, the cube correction, the Fourier-rank law or the full-range torus result. That search does not establish priority.

Evidence, assurance and limitations

The synthetic audio briefing is explanatory, not additional evidence. Its complete transcript is available for reading.

• Proofs. Every theorem has a complete written proof in the 23-page manuscript.
• Computational sanity checks. checks/verify_results.py uses only the standard library. It computes exact rational three-vertex laws by polygon clipping, compares the closed forms for $u_2(r)$ with independent quadrature, and checks two-sided bounds on the torus Fourier coefficient at $d=2$. checks/exact_square_sympy.py verifies $2\sqrt3-2\pi/3$, the exact gap and the cap-variance moment identity in SymPy. A replay from a fresh extraction of the frozen archive reproduced the shipped receipts. Eleven semantic negative controls confirm that the checks reject the earlier coefficient, a raw-volume reading of $\beta$, a wrong three-vertex law, wrong torus bounds and tampered receipts.
• Review. The checking had five stages. First, an internal AI-assisted review in five roles, together with an adversarial review by an outside AI model, produced 41 findings, each with a recorded disposition. Second, a verification re-review checked the revision. Third, a targeted proof audit found every new or rewritten proof correct. Fourth, a second outside-model audit found no error in any coefficient and five gaps in exposition. Finally, the editor fixed those gaps directly, without a further review round. A rating-free summary is in the package. None of this is peer review or independent reproduction.
• Limitations. The results cover a fixed radius only. The coefficient of $n$, shrinking radii, exact unlabelled entropy for $d\ge2$, soft connection functions, nonconvex domains and efficient encoders are open. The paper does not compare its results theorem by theorem with general results on the entropy of random-free graphons, so priority is stated only within the recorded search. The ISIT conference PDF of the source was not inspected.

Who should care, and why

Why the problem matters

Entropy is the floor for lossless compression. For a model as basic as the random geometric graph, the leading cost of storing the network was known only in special cases. The answer turns out to be neither the naive $d\,n\log_2 n$ nor the 2026 conjecture. It is set by two geometric facts: which positions are joined to everyone, and which directions the connection rule can see. Both ideas, universal vertices and effective dimension, should carry over to other latent-position network models.

How to inspect or reproduce the recorded checks

From the GitHub release or the Zenodo archive, with Python 3 and the pinned packages in requirements.txt:

shasum -a 256 -c SHA256SUMS
cd checks
python3 -B verify_results.py --output /tmp/v.json      # asserts on: do not use -O
python3 -B compare_receipts.py /tmp/v.json verification.json
python3 -B exact_square_sympy.py                        # prints the exact square coefficient
cd .. && python3 -B negative_controls.py                # every corruption must be rejected

To check the headline by hand, integrate $4\int_{1/2}^{\sqrt3/2}\bigl(\sqrt{1-a^2}-\tfrac12\bigr)\,da=1+\pi/3-\sqrt3$. AI_INDEX.md maps every theorem to its evidence.

The most valuable next projects

1. Compare the coefficients theorem by theorem with general results on the entropy of random-free graphons and their metric dimension.
2. Identify the coefficient of $n$, even in one dimension or on the circle.
3. Extend the separation and Fourier-rank arguments to radii that shrink with $n$, starting from the explicit remainders in Propositions 3.4 and 5.7.
4. Determine the exact unlabelled (structural) entropy for $d\ge2$, which needs generic results on trivial automorphism groups.
5. Find a polynomial-time encoder that attains $d(1-u_r)\,n\log_2 n+O(n)$ bits.

What is in the evidence package

The package contains the manuscript (PDF and its single self-contained LaTeX source) and the figure with its curve data. It includes the verification script with its receipt, the exact SymPy check, the receipt comparator and the semantic negative controls. It also holds the merged revision response, the final editor fixes and a rating-free review summary; the claim, status, assurance and provenance records, the prior-art record and the citation audit; an agent index; licences (CC0-1.0 for text and data, MIT for code); and SHA-256 manifests. The same files are in the GitHub release and the Zenodo record.

@misc{geometricgraphentropy2026,
  title        = {Universal vertices and effective dimension in geometric-graph entropy},
  author       = {Anonymous},
  year         = {2026},
  doi          = {10.5281/zenodo.23686157},
  url          = {https://doi.org/10.5281/zenodo.23686157},
  version      = {1.1.0-candidate},
  howpublished = {Zenodo},
  note         = {Unrefereed; internally replayed evidence package. Press page: https://evidencepress.org/releases/geometric-graph-entropy/}
}