Wiki
Wiki

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

Updated

Affine coherence and a universal coherent-support bound


These results do not prove the target. They strengthen the available argument for the parameter c(P)c(P) from the convex-fiber note.

Affine-coherent extraction

For an integer set D={a0,…,ah}D=\{a_0,\ldots,a_h\}, call DD affine-coherent if 1\mathbf1 is a vertex of

conv⁡{u∈Z≥0h+1:∑ui=h+1,∑aiui=∑ai}.\operatorname{conv}\{u\in\mathbb Z_{\ge0}^{h+1}: \textstyle\sum u_i=h+1,\quad\sum a_i u_i=\sum a_i\}.

This property is hereditary, by fixing the complementary coordinates at one in any proposed convex decomposition.

Lemma. If the differences ai−a0a_i-a_0, 1≤i≤h1\le i\le h, have distinct 22-adic valuations, then DD is affine-coherent.

In a convex decomposition of 1\mathbf1 into integer fiber points, write r=u−1r=u-\mathbf1 for each participating point. Then

∑iri=0,∑i=1h(ai−a0)ri=0,ri≥−1.\sum_i r_i=0,\qquad \sum_{i=1}^h(a_i-a_0)r_i=0,\qquad r_i\ge-1.

Reduction modulo one power of two beyond the least difference valuation makes the corresponding coefficient rir_i even. It is therefore nonnegative. Its weighted average over the decomposition is zero, so it vanishes at every participating point. Repeat with the next valuation. All nonpivot coefficients vanish, and the degree equation eliminates the pivot coefficient. The decomposition is trivial.

The binary residue tree used in [[research/erdos_963/proof_sketch|the proof sketch]] has a path with at least ⌈log⁡2m⌉\lceil\log_2 m\rceil branching vertices when it has mm leaves. Taking its pivot and one point in each sibling branch proves

caff(P)≥⌈log⁡2∣P∣⌉+1.(1)\boxed{c_{\rm aff}(P)\ge\lceil\log_2|P|\rceil+1.} \tag{1}

This is a statement about affine coherence, not ordinary dissociation.

Transfer from a congruence class

Lemma. Suppose DD is a positive affine-coherent set contained in a+qZa+q\mathbb Z, where q≥2q\ge2 and gcd⁡(a,q)=1\gcd(a,q)=1. If ∣D∣≤q+1|D|\le q+1, then DD is coherent.

Write k=∣D∣k=|D|. Any nonnegative integral representation of ∑D\sum D using DD has total degree congruent to kk modulo qq. If k≤q+1k\le q+1, its only possible degrees below kk are zero or one. Neither is possible when k≥2k\ge2, since ∑D\sum D is positive and is greater than every member of DD. The singleton case is immediate. Thus minimum degree exposes the degree-kk face of the full fiber. Affine coherence makes 1\mathbf1 a vertex of that face, hence of the full fiber.

Consequently, for a nonempty positive integer set BB in one unit class modulo qq,

c(B)≤q⟹∣B∣≤2c(B)−1.(2)\boxed{c(B)\le q\quad\Longrightarrow\quad |B|\le2^{c(B)-1}.} \tag{2}

Otherwise (1) supplies an affine-coherent (c(B)+1)(c(B)+1)-subset, and the transfer lemma makes it coherent.

A universal bound

Let PP be a finite positive integer set and C=c(P)≥2C=c(P)\ge2. Put

q=2⌈log⁡2C⌉.q=2^{\lceil\log_2 C\rceil}.

Order the occupied valuation layers increasingly as P1,…,PrP_1,\ldots,P_r. The established coherence extension across successive valuation layers gives r≤Cr\le C and c(Pi)≤C−i+1c(P_i)\le C-i+1. Scale each layer to odd integers and split it among the q/2q/2 odd classes modulo qq. Each nonempty class has coherent dimension at most C−i+1≤qC-i+1\le q, so (2) gives

∣Pi∣≤(q/2)2C−i.|P_i|\le(q/2)2^{C-i}.

Summation proves

∣P∣≤2⌈log⁡2C⌉−1(2C−1).(3)\boxed{|P|\le 2^{\lceil\log_2 C\rceil-1}(2^C-1).} \tag{3}

For C=1C=1, the separate exact bound is ∣P∣=1|P|=1.

For an arbitrary real set AA with d=d(A)≥2d=d(A)\ge2, first use the established positive integer reduction and then c(P)≤dc(P)\le d. The right side of (3) is increasing in CC. Thus

∣A∣≤2⌈log⁡2d⌉(2d−1)+1.(4)\boxed{|A|\le 2^{\lceil\log_2 d\rceil}(2^d-1)+1.} \tag{4}

Combined with the previously proved bound, this gives

∣A∣≤min⁡{2d+⌊log⁡2(d+1)⌋,2⌈log⁡2d⌉(2d−1)+1}.(5)|A|\le \min\{2^{d+\lfloor\log_2(d+1)\rfloor}, 2^{\lceil\log_2 d\rceil}(2^d-1)+1\}. \tag{5}

This improves the older bound slightly at some dimensions, but still does not give ∣A∣<2d+1|A|<2^{d+1}.

Exact limitation

The transfer argument stops at size q+1q+1: at larger sizes, degree two or larger can occur below the affine fiber. No argument controlling these alternatives across sibling branches of the binary tree has been proved. A long affine-coherent chain alone cannot suffice, as the block construction in the proof sketch already shows for dissociation.