Maximum loneliness on a fixed relation hyperplane

What Lean checks

Original ordered positive distinct sample; deterministic maximum and velocity bound; uniform O(1/N) error over all shifts; fixed and independent Haar-shift laws; exact finite-subspace and positive-N quasipolynomial counts with degree bound; full-support endpoint formula including k=2; sharp (1,2,3) example. The complete 72-module closure passed strict sources, all-owned/private audit and exact stock replay.

Matthias Beck and Samuel Everett ask how maximum loneliness behaves statistically when the speeds satisfy a fixed integer relation. We use their uniform box model from Corollary 3.3, conditioned on that relation. This gives an explicit limiting law for every admissible hyperplane and every shift. Beck and Everett, §4

The law

Write 𝕋=ℝ/ℤ\mathbb T=\mathbb R/\mathbb Z, let ∥x∥\|x\| denote distance to the nearest integer, and put c=(1/2,…,1/2)c=(1/2,\ldots,1/2). Choose a nonzero primitive normal m∈ℤkm\in\mathbb Z^k, k≥2k\ge2. Assume m⊥m^\perp contains a vector of pairwise distinct positive coordinates. Given NN, choose vv uniformly among ordered vectors of pairwise distinct integers in [1,N]k[1,N]^k satisfying m⋅v=0m\cdot v=0. Define

L(v,s)=maxt∈𝕋mini∥si+tvi∥,Lm(s)=12−∥m⋅(c−s)∥∥m∥1.L(v,s)=\max_{t\in\mathbb T}\min_i\|s_i+t v_i\|,\qquad L_m(s)=\frac12-\frac{\|m\cdot(c-s)\|}{\|m\|_1}.

Theorem. Every sampled vector satisfies L(v,s)≤Lm(s)L(v,s)\le L_m(s) for every s∈𝕋ks\in\mathbb T^k. For each fixed ε>0\varepsilon>0,

Pr(sups∈𝕋k[Lm(s)−L(v,s)]≥ε)=Om,ε(N−1).\Pr\!\left(\sup_{s\in\mathbb T^k}\big[L_m(s)-L(v,s)\big]\ge\varepsilon\right) =O_{m,\varepsilon}(N^{-1}).

Thus a fixed shift has limiting distribution concentrated at Lm(s)L_m(s). In particular the unshifted limit is 1/21/2 if the coordinate sum of mm is even and 1/2−1/(2∥m∥1)1/2-1/(2\|m\|_1) if it is odd. An independent Haar-uniform shift gives a uniform limiting distribution on [1/2−1/(2∥m∥1),1/2][1/2-1/(2\|m\|_1),1/2], since m⋅(c−s)m\cdot(c-s) is Haar-uniform on the circle. Dividing an input normal by its coordinate gcd before using the formula is essential.

The unconditioned random-speed problem was studied by Czerwiński. Giri and Kravitz study loneliness through distances from subtori to the center of the cube. The finiteness principle for subgroups avoiding an open set goes back to Lawrence. The argument below proves the connected-subgroup case it uses. We claim no priority for these tools. Czerwiński · Giri and Kravitz · Lawrence

Proof

Let V=m⊥V=m^\perp, Λ=V∩ℤk\Lambda=V\cap\mathbb Z^k, and let HH be the image of VV in 𝕋k\mathbb T^k. Then H={x:m⋅x=0(mod1)}H=\{x:m\cdot x=0\pmod 1\}. Indeed, if a lift of xx has integral dot product with mm, Bézout's identity lets us subtract an integer vector with that same dot product. In particular H=V/ΛH=V/\Lambda is connected.

Use the maximum of the circular coordinate distances as the torus metric. On the circle ∥u∥=1/2−∥u−1/2∥\|u\|=1/2-\|u-1/2\|, so L(v,s)L(v,s) is 1/21/2 minus the distance from c−sc-s to the circle Cv={tv:t∈𝕋}C_v=\{tv:t\in\mathbb T\}. That circle lies in HH. For any yy, the distance from yy to HH is exactly ∥m⋅y∥/∥m∥1\|m\cdot y\|/\|m\|_1. The lower bound follows from the triangle inequality. For equality choose b∈[−1/2,1/2]b\in[-1/2,1/2] representing m⋅ym\cdot y modulo one, then subtract the vector with coordinates bsgn(mi)/∥m∥1b\,\mathrm{sgn}(m_i)/\|m\|_1 from yy. The resulting point lies in HH. This proves the deterministic upper bound and computes the maximum on the containing torus.

We next show that a typical CvC_v is dense to within ε/2\varepsilon/2 in HH. The following argument also works inside the image TUT_U of any rational linear subspace UU. Fix a nonempty relatively open set B⊂TUB\subset T_U. Take a continuous nonnegative function supported in BB of Haar integral a>0a>0. Approximate it uniformly within a/4a/4 by a trigonometric polynomial restricted from the ambient torus. Such polynomials are dense by Stone–Weierstrass, since the coordinate characters separate points. A character with frequency b∈ℤkb\in\mathbb Z^k has mean one on CvC_v exactly when b⋅v=0b\cdot v=0, and mean one on TUT_U exactly when b⊥Ub\perp U. In each other case its mean is zero.

If v∈Uv\in U avoids the finitely many hyperplanes b⊥∩Ub^\perp\cap U arising from polynomial frequencies b⊥̸Ub\not\perp U, the polynomial has equal integrals on CvC_v and TUT_U. The original function then has integral at least a/2a/2 on CvC_v. Thus every circle missing BB has its velocity in a finite union of proper rational subspaces of UU.

Cover HH by finitely many relative balls of radius ε/4\varepsilon/4. A circle meeting every ball comes within ε/2\varepsilon/2 of every point. Apply the preceding paragraph to each ball. In the sampling box, VV contributes Θm(Nk−1)\Theta_m(N^{k-1}) admissible lattice points. Indeed, Λ\Lambda has rank k−1k-1 and the scaled region in VV has positive relative volume by admissibility. Its boundary and the excluded coordinate-equality hyperplanes have measure zero. A proper rational subspace contributes Om(Nk−2)O_m(N^{k-2}) points, for instance by injecting its lattice points into a choice of independent integer coordinates. For the finite list the implicit constant can depend on ε\varepsilon. Outside their union, every distance to CvC_v differs from the distance to HH by at most ε/2\varepsilon/2, simultaneously for all target points. This proves the theorem, including the supremum over shifts.

Counts below a fixed threshold

For fixed ss and real u<Lm(s)u\lt L_m(s), the admissible vectors with L(v,s)≤uL(v,s)\le u form the intersection of the sample with a finite union of proper rational subspaces of VV. To see exact equality of sets, begin at U=VU=V. If the maximum on s+TUs+T_U is at most uu, retain UU in full. Otherwise the points of TUT_U where the shifted loneliness exceeds uu form a nonempty relatively open set. The open-set argument places every exception in a finite union of proper subspaces of UU. Repeat inside each one. Each step reduces dimension, so the finite tree terminates. Every retained subspace satisfies the threshold everywhere. It is harmless to include or discard the zero speed vector before intersecting with the sample.

Consequently the exceptional count is a quasipolynomial in the integer N≥1N\ge1, of degree at most k−2k-2 whenever it is nonzero. Apply inclusion–exclusion to the retained subspaces, the forbidden coordinate equalities, and the coordinate-zero faces of [0,N]k[0,N]^k. Each closed piece is the NN-fold dilate of a rational polytope and its lattice-point count is an Ehrhart quasipolynomial. The denominator of the conditional probability is a quasipolynomial by the same argument. Beck and Robins, Computing the Continuous Discretely, Chapter 3

The order N−1N^{-1} can occur. On v1+v2=v3v_1+v_2=v_3 the unshifted limit is 1/31/3. All ⌊N/3⌋\lfloor N/3\rfloor positive multiples of (1,2,3)(1,2,3) have loneliness 1/41/4. For g(1,2,3)g(1,2,3), time 1/(4g)1/(4g) attains 1/41/4. The upper bound follows from the gap principle for 0,t,2t,3t0,t,2t,3t and invariance under common scaling. There are Θ(N2)\Theta(N^2) admissible triples.

How often the endpoint is attained

Suppose s=0s=0 and every mim_i is nonzero. Put d=k−1d=k-1, A=∥m∥1A=\|m\|_1, and Q=2Q=2 if AA is even or Q=AQ=A if AA is odd. Then

limN→∞Pr(L(v,0)=Lm(0))=φ(Q)Qd∏p∣Q(1−p−d).\lim_{N\to\infty}\Pr\big(L(v,0)=L_m(0)\big) =\frac{\varphi(Q)}{Q^d\prod_{p\mid Q}(1-p^{-d})}.

For even AA the maximizing point on HH is cc, of order two. For odd AA the two maximizing points are c±sgn(m)/(2A)c\pm\mathrm{sgn}(m)/(2A). Indeed equality in the distance bound requires every nonzero coefficient to use the full coordinate displacement with a consistent sign. The two points are negatives on the torus. Each has order AA, since (A±1)/2(A\pm1)/2 is coprime to AA. Thus in both cases it suffices that the circle contain one specified point yy of order QQ.

Choose a lattice basis of Λ\Lambda. It identifies HH with 𝕋d\mathbb T^d and identifies yy with b/Qb/Q, where gcd(b1,…,bd,Q)=1\gcd(b_1,\ldots,b_d,Q)=1. Write v=gwv=g w with ww primitive in Λ\Lambda. Its circle is the circle of ww. Bézout's identity for the coordinates of ww implies that the parameter of an order-QQ point on that circle has reduced denominator QQ. Hence y∈Cvy\in C_v exactly when wmodQw\bmod Q is a unit multiple of bb.

For d≥2d\ge2 the primitive directions arising from all sampled velocities are asymptotically uniform among the primitive residue classes modulo QQ. Here are the counting details. In the chosen lattice coordinates the sample is the dilation of a fixed bounded rational region with finitely many hyperplanes removed and with positive volume DD. In a particular primitive residue class, Möbius inversion for the common divisor gives primitive-point density

DQd∑(h,Q)=1μ(h)hd=DQd∏p∤Q(1−p−d)\frac{D}{Q^d}\sum_{(h,Q)=1}\frac{\mu(h)}{h^d} =\frac{D}{Q^d}\prod_{p\nmid Q}(1-p^{-d})

per NdN^d. For fixed hh coprime to QQ, dividing by hh gives one residue class in a box scaled by N/hN/h. The lattice Riemann sum gives the term displayed. The scaled nonzero lattice count is O((N/h)d)O((N/h)^d) for h≤CNh\le C N and zero thereafter, since all coordinates are bounded by CNCN in lattice coordinates. This summable bound justifies the limit. Summing over all multiples gwg w preserves uniformity by the same bound with gg in place of hh. There are Qd∏p∣Q(1−p−d)Q^d\prod_{p\mid Q}(1-p^{-d}) primitive classes by the Chinese remainder theorem, and precisely φ(Q)\varphi(Q) unit multiples of bb. In dimension one every sampled circle is HH and the displayed ratio equals one. This proves the endpoint formula.

For example, on v1+v2=v3v_1+v_2=v_3 the limiting probability of exactly 1/31/3 is 2/(9−1)=1/42/(9-1)=1/4. All but a vanishing fraction lie arbitrarily close to 1/31/3.