Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Mobile anchors and triangular gluing
Motivation and exact remaining requirement
In every proper -coloring of a configuration with coloring number exactly , each pair of color classes has a nonzero common signed sum: otherwise their union is dissociated and the two colors can be merged. These pairwise sums may depend on the coloring and need not be roots. They offer a possible replacement for the universal anchors lost by simplex gluing.
The constructions below control the entire rational ternary closure, not merely planted rows. For a fixed source with finite , they exclude triangular padding whose buffer lengths all exceed the explicit source-dependent threshold below. They do not exclude shorter buffers, changing sources with changing thresholds, or sources with . Recurrent constraint interaction is a possible way to leave this excluded class, not a proved necessary feature of every successful construction.
Arbitrary mobile words eventually separate — proved
Let , , and . Set
For any nonzero rational anchor word , , there are proper base colorings satisfying, for every color ,
Fix a -element separating family of colorings. After choosing the first coloring, at most nonzero pairs remain. At any later block each surviving pair is omitted by at least one member of the family. A greedy choice reduces the survivor count by a factor at most . After steps the count is less than one.
If has points and entries bounded by , then : a rational line's integer points are integer multiples of a primitive vector, and a nonzero coordinate bounds the possible multipliers of any signed sum by .
A precise triangular construction
Take independent copies of . Let integral gluing rows be . Give each row a buffer set of size , with the sets pairwise disjoint. Assume that on every , row has a primitive nonzero anchor , while every later row , , vanishes. Earlier rows may overlap these buffers. Quotient by the rational span of all rows, and denote the image family by . Put , using primitive width.
Saturation and distinctness
Choose one primitive pivot from each buffer set. Integer functionals taking value one on those pivots give a unitriangular minor of the row matrix. Thus the rows generate a saturated lattice; the quotient group is free. In a nonzero rational row combination, its least active row has nonzero entries on every one of its buffers, since all later rows vanish there. If every , the combination has at least three nonzero blocks. Consequently each block embeds, and no new zero, equal, or antipodal labels occur between blocks.
Uniform analytic bound
Exactly as in primitive-anchor phase gluing,
Independently maximize every block polynomial. Correct row constraints in reverse order, spreading a principal phase across its buffers with the separate minimizing functionals . Later rows are unaffected because they vanish on these buffers. The disjoint buffer sets mean every polynomial block moves only once from its independent maximum. Its first-order variation vanishes, and its quadratic loss is bounded by times its coefficient mass. Summing gives (2), with a maximum rather than a sum over rows.
Nevertheless the quotient has no chromatic increase
If every , then . Color each buffer word using (1) and color all remaining blocks properly. Suppose a nonzero monochromatic relation had block-sum vector . On the buffers of its least active row , its sums are exactly . Equation (1) forces , a contradiction. If , blockwise properness already makes the relation trivial. Restriction to an embedded block gives the matching lower bound .
This proof permits arbitrary mobile labels, not just a finite list of directions. Its no-increase conclusion requires both finite and for every buffer. Analytic smallness alone does not imply these inequalities, so the theorem does not rule out every cheap triangular gluing or every iteration with changing sources.
A full-closure counting criterion without triangularity
For as above, let have dimension , and suppose every nonzero vector of has at least nonzero blocks. The quotient image family is -colorable whenever
Color blocks independently from the fixed -witness family. A coordinate projection onto scalar coordinates injects on , so . Each fixed nonzero vector has probability at most of belonging to the signed spans of a fixed color in all blocks. A union bound over these vectors and the colors proves (3); zero block sums are excluded by blockwise properness. Again the count covers all induced relations, not just a selected row list.