Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Quadratic-loss primitive-anchor gluing


Standing

The analytic lemma below is author-recorded; a separate reviewer checked it internally, which is not a tier. It improves the available estimate for a particular gluing operation. It does not supply iterated chromatic growth: a non-antipodal example below shows that even arbitrarily inexpensive boundary gluing can destroy every universal anchor.

Primitive normalization

Let BB be a finite set of nonzero elements of a free abelian group Γ=⟨B⟩Z\Gamma=\langle B\rangle_{\mathbb Z}, with no antipodal pair. Suppose χ(B)=q\chi(B)=q and a nonzero w∈Γw\in\Gamma belongs to Σ(C)\Sigma(C) for every class CC of every proper qq-coloring. Write w=kuw=ku, where uu generates the rank-one group Γ∩Qw\Gamma\cap\mathbb Qw, and kk is a nonzero integer. Thus uu is primitive in Γ\Gamma. Define

λB(u)=min⁡ℓ(u)=1max⁡b∈B∣ℓ(b)∣,ℓ∈Hom⁡(Γ,R).(1)\lambda_B(u)=\min_{\ell(u)=1}\max_{b\in B}|\ell(b)|, \qquad \ell\in\operatorname{Hom}(\Gamma,\mathbb R). \tag{1}

The minimum exists: because BB spans Γ⊗R\Gamma\otimes\mathbb R, max⁡B∣ℓ(b)∣\max_B|\ell(b)| is a norm, and its sublevel sets are compact.

For m≥3m\geq3, form the torsion-free group

Γm=Γm/Z(u1+⋯+um)\Gamma_m=\Gamma^m/\mathbb Z(u_1+\cdots+u_m)

and let GmG_m be the union of the images of BB in its mm summands. Primitivity of uu implies that the displayed quotient is free abelian. The copies of BB remain distinct and nonzero, with no new antipodal pairs: a relation between at most two summands cannot be a nonzero multiple of u1+⋯+umu_1+\cdots+u_m.

The primitive normalization is essential. Quotienting by w1+⋯+wmw_1+\cdots+w_m without saturation can leave torsion and is not the rational-vector gluing used for positive-integer realization. In particular, one cannot replace λB(u)\lambda_B(u) by λB(w)\lambda_B(w) in the bound below.

Analytic gluing lemma — proved

Use the positive-real Sidon parameter ρ\rho defined in the tensor extraction theorem. Then

ρ(Gm)≥ρ(B)−π2λB(u)22m2.(2)\rho(G_m)\geq\rho(B)- \frac{\pi^2\lambda_B(u)^2}{2m^2}. \tag{2}

Indeed, the character tuples on Γm\Gamma_m are precisely (g1,…,gm)∈Γ^m(g_1,\ldots,g_m)\in\widehat\Gamma^m such that ∏iu(gi)=1\prod_i u(g_i)=1. Write an arbitrary polynomial on GmG_m as ∑ifi(gi)\sum_i f_i(g_i), and independently maximize Re⁡fi\operatorname{Re}f_i on each torus. The resulting value is at least ρ(B)\rho(B) times the sum of the absolute values of all coefficients.

Choose θ∈[−π,π]\theta\in[-\pi,\pi] with eiθ=(∏iu(gi))−1e^{i\theta}=(\prod_i u(g_i))^{-1}, and choose a minimizing ℓ\ell in (1). Replace each gig_i by the character

gi′(γ)=gi(γ)exp⁡(iθℓ(γ)/m).g'_i(\gamma)=g_i(\gamma) \exp(i\theta\ell(\gamma)/m).

Their product constraint now holds because ℓ(u)=1\ell(u)=1. At the independent maximum of Re⁡fi\operatorname{Re}f_i, its derivative in the ℓ\ell direction vanishes. Applying Re⁡(zeit)≥Re⁡z−tIm⁡z−∣z∣t2/2\operatorname{Re}(ze^{it})\geq\operatorname{Re}z -t\operatorname{Im}z-|z|t^2/2 term by term therefore bounds the total loss by

θ22m2∑i,b∣ci,b∣ℓ(b)2≤π2λB(u)22m2∑i,b∣ci,b∣.\frac{\theta^2}{2m^2}\sum_{i,b}|c_{i,b}|\ell(b)^2 \leq \frac{\pi^2\lambda_B(u)^2}{2m^2} \sum_{i,b}|c_{i,b}|.

This proves (2), without a randomized lattice lift.

For m≥q+1m\geq q+1, the coloring number is exactly q+1q+1. Under a putative qq-coloring, each block class signed-spans ww, and their representations sum to zero in the quotient. Conversely, use q+1q+1 colors, a proper qq-palette in every block, and arrange that every color is absent from a block. Any proper collection of block summands embeds as a direct sum in the quotient, so every resulting class is dissociated.

Cheap boundary gluing need not propagate an anchor — proved

Let A⊂Z>0A\subset\mathbb Z_{>0} have gcd one, maximum MM, coloring number q≥2q\geq2, and a universal anchor a≠0a\ne0. The punctured Grow–Whicher example in anchor gluing supplies such an AA, with q=2q=2, a=3a=3, and M=253M=253.

For an integer r≥2r\geq2, put

B=⨆j=1rAej⊂Zr,w=a(e1+⋯+er),u=e1+⋯+er.B=\bigsqcup_{j=1}^r A e_j\subset\mathbb Z^r, \qquad w=a(e_1+\cdots+e_r),\qquad u=e_1+\cdots+e_r.

Direct sums preserve the coloring number and the hereditary dissociation constant. The vector ww is universal: restrict any proper qq-coloring to each summand, represent aejae_j in the given color, and add the disjoint representations. Moreover

ρ(B)=ρ(A),λB(u)=M/r.(3)\rho(B)=\rho(A),\qquad \lambda_B(u)=M/r. \tag{3}

The first equality follows by independently maximizing the polynomials on the summands. For the second, write ℓ(ej)=tj\ell(e_j)=t_j. The constraint is ∑jtj=1\sum_jt_j=1, while the objective is Mmax⁡j∣tj∣M\max_j|t_j|; its minimum M/rM/r is attained at tj=1/rt_j=1/r.

Apply the boundary gluing m=q+1m=q+1 to (B,w)(B,w). Its rmrm coordinate rays have exactly the one relation that their sum is zero. Consequently the output is exactly

Gm≅A⊗Sr(q+1).(4)G_m\cong A\otimes S_{r(q+1)}. \tag{4}

It has coloring number q+1q+1, and (2) has loss π2M2/[2r2(q+1)2]\pi^2M^2/[2r^2(q+1)^2], tending to zero as r→∞r\to\infty. Nevertheless r(q+1)≥q+2r(q+1)\geq q+2, so the proved large-simplex obstruction says that it has no nonzero universal anchor for (q+1)(q+1)-colorings, even after any exact ternary-relation-preserving scalar encoding.

Thus non-antipodality, hereditary extraction, and arbitrarily small analytic loss do not imply boundary-anchor propagation. This does not rule out a more structured scalar boundary construction; that narrower problem remains open here.