One more dimension in the unit-congruence bound

---

This note improves a universal bound but does not resolve Erdős 963. The notation $d(P)$ denotes maximum dissociation dimension, not the minimum size of an inclusion-maximal dissociated subset.

Extension theorem

Theorem. Let $q\ge4$ be even, and let $O$ be a finite set of positive integers in one residue class $a\pmod q$, where $\gcd(a,q)=1$. If $d(O)\le q+1$, then

$$|O|\le2^{d(O)-1}. \tag{1}$$

The case $d(O)\le q$ follows from affine-coherent extraction and congruence transfer. Indeed, if the count fails, extraction gives an affine-coherent $(d(O)+1)$-subset, and the transfer lemma makes it coherent and hence dissociated. We prove the remaining case $d=q+1$.

Split $O=A\sqcup B$ into its two residue classes modulo $2q$. If one is empty, the same transfer argument, now modulo $2q$, proves (1). Assume both are nonempty.

Suppose $D\subseteq A$ is dissociated and $|D|=d$, and put $S=\sum D$. Every $b\in B$ has a ternary representation on $D$. If its coefficient sum is $s$, reduction modulo $2q$ gives

$$s\equiv q+1=d\pmod{2q},\qquad -d\le s\le d.$$

The only possibilities are $s=d$ and $s=2-d$. The former representation is all-plus. In the latter, positivity excludes all-negative representations, leaving exactly one positive and $d-1$ negative coefficients. Thus

$$b=S\quad\hbox{or}\quad b=2x-S\quad(x\in D). \tag{2}$$

At most one value of the second kind is positive. Consequently, if $d(A)=d$, then $|B|\le2$. The same assertion holds with the two fibers interchanged.

If both fibers have at least three elements, they therefore have dimension at most $d-1=q$. Apply the already proved unit-class bound modulo $q$ to each: their total size is at most $2^{d-1}$. It remains to treat a fiber $B$ of size one or two.

If $d(A)\le d-1$, then $|O|\le2^{d-2}+2\le2^{d-1}$, so suppose $d(A)=d$. When $B=\{b,c\}$, equation (2) shows that every maximum $d$-subset of $A$ contains

$$x=(b+c)/2.$$

Deleting $x$ lowers the dimension of $A$ to at most $d-1$. Applying the unit-class bound to $A\setminus\{x\}$ gives

$$|O|\le2^{d-2}+3\le2^{d-1},$$

since $d\ge5$.

The singleton fiber

Let $B=\{b\}$. By a circuit we mean a nonzero ternary relation whose support contains no smaller support of a nonzero ternary relation. Consider all circuits on $O$ of support size at most $d+1$.

Every such circuit contained in $A$ is balanced: its coefficient sum is divisible by $2q$, and its absolute value is at most $d+1=q+2<2q$. A circuit through $b$, oriented as $b=\sum_{x\in A}\varepsilon_xx$, has at most $d$ other coordinates. The same congruence and positivity argument as in (2) gives exactly two possible forms:

$$b=\sum_{x\in E}x,\quad |E|=d, \qquad\hbox{or}\qquad b=x-\sum_{y\in E'}y,\quad |E'|=d-1. \tag{3}$$

If $b>\max A$, only the first form is possible. If $b<\max A$, the first form is impossible as well: circuit minimality makes its $d$ summands dissociated, and adjoining $\max A>b=\sum E$ would give a dissociated $(d+1)$-set. Thus all circuits through $b$ have the same coefficient sum on $A$, namely $d$ when $b>\max A$ and $2-d$ when $b<\max A$.

Let $R\subseteq\mathbb Z^O$ be generated by the circuits just considered, and put $H=\mathbb Z^O/R$. Two integer functionals annihilate $R$: the actual weights and the function $h$ equal to one on $A$, with

$$h(b)=d\quad(b>\max A),\qquad h(b)=2-d\quad(b<\max A).$$

These functionals are rationally independent, since $A$ contains at least two distinct weights. Hence $\operatorname{rank}H\ge2$. In particular $\dim_{\mathbb F_2}(H/2H)\ge2$.

The actual odd weights give a character $\lambda:H\to\mathbb F_2$ equal to one on every coordinate column. Choose a character $\chi\notin\{0,\lambda\}$. Its values partition $O$ into two nonempty classes $O_0,O_1$. Both have dimension at most $d-1$. For if a dissociated $d$-set lay in $O_0$, adjoining a point of $O_1$ would produce a circuit of size at most $d+1$ using that point; applying $\chi$ contradicts that relation. For a $d$-set in $O_1$, apply $\chi+\lambda$ instead.

The classes are still subsets of the original unit class modulo $q$. The established bound at dimension at most $q=d-1$ gives $|O_0|,|O_1|\le2^{d-2}$. This proves (1).

A recursive universal estimate

For $d\ge1$ put

$$B_d=\min\left\{ 2^{d+\lfloor\log_2(d+1)\rfloor-1}-1, 2^{\lceil\log_2d\rceil-1}(2^d-1) \right\},$$

where the second term is omitted for $d=1$. These are the previously proved positive-set bounds: the first follows by applying the binary-tree bound to $\{0\}\cup P\cup(-P)$, and the second is the coherent-support bound.

Set $U_0=0$, $U_d=2^d-1$ for $1\le d\le4$, and, for $d\ge5$,

$$q_d=2^{\lceil\log_2(d-1)\rceil},\qquad U_d=\min\{B_d,\ q_d2^{d-2}+U_{d-1}\}. \tag{4}$$

Then every finite positive real set of dimension at most $d$ has at most $U_d$ elements, and every finite real set of dimension at most $d$ has at most $2U_d+1$ elements.

To prove this, use the established integer realization and divide by the largest common power of two. The resulting positive set has a nonempty odd part. Its even part has dimension at most $d-1$, because one odd element can be adjoined to every dissociated even subset. Partition the odd part into its $q_d/2$ unit classes modulo $q_d$. The theorem bounds each by $2^{d-1}$, since $d\le q_d+1$. This proves the second term of (4), and $B_d$ supplies the first. Symmetrization proves the real-set bound.

The first new values are

$$\begin{array}{c|rrrrr} d&5&6&7&8&9\\\hline U_d&47&127&383&895&1919\\ 2U_d+1&95&255&767&1791&3839. \end{array}$$

In particular every $96$-element real set contains a dissociated six-set. This still does not prove the required six-set for every $64$-element real set. Equivalently, the estimate $U_5=47$ does not give the target positive bound $U_5=31$.

The remaining unit-congruence gap begins at $d=q+2$. A ternary representation across the two modulo-$2q$ fibers can then omit a coordinate of a maximum set, and the full-support argument (2), as well as the singleton circuit argument, no longer applies.

Sharpening by the new affine theorem

The subsequent eight-point affine theorem improves the unit-class count, for $4\le d\le q+1$, to $7\,2^{d-4}$. Thus (4) can be strengthened: keep $U_0=0$ and $U_d=2^d-1$ for $1\le d\le4$, and replace its recursion by

$$\boxed{U_d=\min\{B_d,\ 7q_d2^{d-5}+U_{d-1}\} \qquad(d\ge5).} \tag{5}$$

The proof is the same parity split. The first values are now

$$\begin{array}{c|rrrrr} d&5&6&7&8&9\\\hline U_d&43&127&351&799&1695\\ 2U_d+1&87&255&703&1599&3391. \end{array}$$

In particular every $88$-element real set has a dissociated six-set, but the requested threshold is $64$, still unproved.

The same note proves the unmodified unit-class count through $d\le q+2$ for even $q\ge6$, through $d\le q+3$ for even $q\ge10$, and through $d\le\lfloor4q/3\rfloor$ for even $q\ge56$. Those additional congruence ranges can further lower the odd-part term at some dimensions; they do not establish the bound for unrestricted odd sets. The concrete endpoint $q=4,d=6$ was left unresolved by these arguments; it is settled, with bound $31$, by the grid theorem.

Current strengthened recursion

The later fourteen-point theorem gives the affine bound $13\,2^{d-5}$ for $d\ge5$. For even $q\ge6$ the unit-class argument above propagates that same bound through $d=q+1$: both dropped classes contribute $13\,2^{d-6}$, and the two-point exception contributes at most $13\,2^{d-6}+3\le13\,2^{d-5}$. The already proved case $d\le q$ follows directly from the affine theorem. The $q=4,d=5$ endpoint retains its proved bound fourteen, not thirteen.

Combining these facts with [[research/erdos_963/positive_seven|the sharp positive dimension-three bound]] and the grid theorem gives the following current recursion. Set

$$(U_0,U_1,U_2,U_3,U_4,U_5,U_6)=(0,1,3,6,14,42,104),$$

and for $d\ge7$ set

$$\boxed{U_d=\min\{B_d,\ 13q_d2^{d-6}+U_{d-1}\}, \qquad q_d=2^{\lceil\log_2(d-1)\rceil}.} \tag{6}$$

Then $|P|\le U_{d(P)}$ for positive sets, and $|A|\le2U_{d(A)}+1$ for arbitrary real sets.

For the new starting values, the established odd bounds through dimension four are $1,2,4,8$. The sharp positive bound $U_3=6$ therefore gives $U_4=8+6=14$. Splitting an odd dimension-five set modulo four gives at most $28$ elements, hence $U_5=28+14=42$. The grid theorem bounds each modulo-four class of a dimension-six odd set by $31$, so its size is at most $62$ and $U_6=62+42=104$. Each use of the even-part bound is justified by adjoining an odd element after normalization. For $d\ge7$, there are $q_d/2$ odd classes, each bounded by $13\,2^{d-5}$, proving (6).

In particular,

$$\begin{array}{c|rrrrrrr} d&3&4&5&6&7&8&9\\\hline U_d&6&14&42&104&312&728&1560\\ 2U_d+1&13&29&85&209&625&1457&3121. \end{array}$$

Thus every $86$-element real set has a dissociated six-set, and every $210$-element real set has a dissociated seven-set. The required thresholds $64$ and $128$ remain unproved.