Wiki
Wiki

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

Updated

Exact eventual defect for a fixed simplex base


Theorem

Let BB be a finite nonempty set of nonzero rational vectors, and let a=rdiss(B)a=r_{\rm diss}(B). There is an integer d(B)d(B), with 1≤d(B)≤a1\leq d(B)\leq a, such that

rdiss(B⊗Sp)=pa−d(B)for every integer p≥(3a+1)/2.(1)r_{\rm diss}(B\otimes S_p)=pa-d(B) \quad\text{for every integer }p\geq(3^a+1)/2. \tag{1}

If a≥2a\geq2, then d(B)≥2d(B)\geq2. Indexed simplexes of size two are allowed when a=1a=1; the application to odd prime factors uses p≥3p\geq3.

This is an exact fixed-base result, not a bound on the chromatic number of the changing bases in the main argument.

Proof

Use the signed-span layer criterion, and define

d(B)=min⁡{∑i=1t(a−∣Ci∣):t≥1, Ci⊆B dissociated, ⋂i=1tΣ(Ci)={0}}.(2)d(B)=\min\left\{\sum_{i=1}^t(a-|C_i|): t\geq1,\ C_i\subseteq B\text{ dissociated},\ \bigcap_{i=1}^t\Sigma(C_i)=\{0\}\right\}. \tag{2}

All costs are nonnegative integers; a single empty slice has cost aa, so the minimum exists and is at most aa.

Choose a minimizing family and retain its first slice C1C_1. For each pair {u,−u}\{u,-u\} of nonzero elements of Σ(C1)\Sigma(C_1), retain one slice whose signed span excludes uu; it also excludes −u-u. The retained intersection is still zero. There are at most

1+∣Σ(C1)∣−12≤3a+121+\frac{|\Sigma(C_1)|-1}{2}\leq\frac{3^a+1}{2}

retained slices. Discarding other slices cannot increase the cost, and the definition of d(B)d(B) prevents it from decreasing. Pad with maximum dissociated subsets to obtain exactly pp slices. Each added slice has zero cost and leaves the intersection zero. The layer criterion gives a dissociated set of size pa−d(B)pa-d(B). Conversely, the slices of any dissociated subset of B⊗SpB\otimes S_p are an admissible family in (2), proving the upper bound and (1).

Every maximum dissociated subset CC satisfies B⊆Σ(C)B\subseteq\Sigma(C). Indeed, adjoining b∈B∖Cb\in B\setminus C produces a ternary relation, necessarily with nonzero coefficient on bb. Thus a zero-cost family cannot have zero intersection, proving d(B)≥1d(B)\geq1. A cost-one family has just one deficient slice of size a−1a-1, with all others maximum. If a≥2a\geq2, any point of that deficient slice is a nonzero element of every signed span. This excludes cost one.

Source check and exact scope

After its digest, the reading copy of Ramsey–Graham, Permutation and extension for planar quasi-independent subsets of the roots of unity, the source this section compares against, was checked at Theorems 1.2.2 and 4.1.1 and the latter's proof. For odd squarefree mm, Theorem 1.2.2 gives, for primes q>pq>p with p,q∤mp,q\nmid m,

Ψ(qm)≥Ψ(pm)+(q−p)Ψ(m).\Psi(qm)\geq\Psi(pm)+(q-p)\Psi(m).

Thus pΨ(m)−Ψ(pm)p\Psi(m)-\Psi(pm) is already a nonincreasing nonnegative integer and eventually stabilizes. The elementary proof above supplies an explicit threshold and variational formula for its limiting value, and also applies to nonprime simplex sizes.

The proof of the source's extension theorem uses only dissociation of each new layer, although its statement asks for maximum-size new layers. Applied color by color, or directly by the layer criterion, it shows

χ(B⊗Sq)≤χ(B⊗Sp)(q≥p≥3).\chi(B\otimes S_q)\leq\chi(B\otimes S_p)\qquad(q\geq p\geq3).

Keep the old layers and add arbitrary properly colored base layers. Existing signed-span intersections stay zero. This is replacement of a factor of a fixed base; it is not monotonicity under adjoining a new prime factor.

Neither d(B)d(B) nor the threshold in (1) is uniform as BB grows. The theorem supplies no fixed coefficient height with infinite coloring number. Its proof received an independent internal check; no computation or external review is claimed.