On the size of dissociated bases

../

theorem_1: For a positive integer n, the set of 0-1 vectors in Z^n contains a dissociated subset, one whose subset sums are pairwise distinct, of size (1+o(1)) n log_2 n / log_2 9 as n tends to infinity.

theorem_2: If Λ and M are maximal dissociated subsets of a finite subset A of an abelian group with A not contained in {0}, then |M|/log_2(2|M|+1) ≤ |Λ| < |M|(log_2(2|M|) + log_2 log_2(2|M|) + 2).

theorem_3: If A is a finite subset of an abelian group G of exponent e and r is the rank of the subgroup generated by A, then every maximal dissociated subset Λ of A satisfies r ≤ |Λ| ≤ r log_2 e.

---

Vsevolod F. Lev, Raphael Yuster, "On the size of dissociated bases," arXiv:1005.0155 (2010); published in Electron. J. Combin. 18(1) (2011), #P117, DOI 10.37236/604 (Crossref record read).

Source: arXiv:1005.0155. The copy read for this card is a five-page pdfTeX PDF (MiKTeX, created 27 April 2011 per its metadata; 253,732 bytes) with a text layer, whose p. 1 carries the title "On the size of dissociated bases", the authors and the abstract and no arXiv stamp, so which arXiv version it corresponds to is unrecorded. Provenance: a survey download of September 2026; the download URL was not recorded. The theorem statements were checked against p. 2 of that PDF, and the page locators below are the PDF's. The PDF prints no notice and carries no arXiv stamp, so which copy it is remains unrecorded; the arXiv abstract page names arXiv's non-exclusive distribution license for its only version, v1 (https://arxiv.org/abs/1005.0155v1, read 2026-10-02), and the term is taken from it, every other right reserved.

Main results

Let a subset of an abelian group be dissociated when all of its subset sums are distinct.

• Theorem 1 (result page). For a positive integer $n$, the Boolean cube $\{0,1\}^n\subseteq\mathbb Z^n$ has a dissociated subset of size

$$(1+o(1))\frac{n\log_2 n}{\log_2 9}\qquad(n\to\infty).$$

Stated on p. 2; the proof runs from p. 2 to p. 4.

• Theorem 2 (result page). Let $A\nsubseteq\{0\}$ be a finite subset of an abelian group, and let $\Lambda$ and $M$ be two of its maximal dissociated subsets. Then

$$\frac{|M|}{\log_2(2|M|+1)}\leq |\Lambda| <|M|\bigl(\log_2(2|M|)+\log_2\log_2(2|M|)+2\bigr).$$

The print has $\log_2(2M)$ in the first term of the upper bound, a misprint for $\log_2(2|M|)$: the proof's last display (p. 5) has $\log_2(2|M|)$ there and $\log_2(5/2)<2$ in place of $2$. Thus two inclusion-maximal dissociated subsets of the same finite set differ by at most a logarithmic factor. Stated on p. 2; the counting argument runs from p. 4 to p. 5.

• Theorem 3 (result page). If $A$ is a finite subset of an abelian group $G$ of exponent $e=\exp(G)$ and $r$ is the rank of the subgroup $\langle A\rangle$, then every maximal dissociated $\Lambda\subseteq A$ has $r\leq|\Lambda|\leq r\log_2 e$. Stated on p. 2; the two-line proof is on p. 5.

The paper closes (p. 5) with an open problem: the values of $\liminf$ and $\limsup$ of $L_n/(n\log_2 n)$, where $L_n$ is the largest size of a dissociated subset of $\{0,1\}^n$; Theorems 1 and 2 place both between $1/\log_2 9$ and $1$.

Construction and basis comparison

For Theorem 1, the authors seek $m$ dissociated columns in an $n\times m$ $0$-$1$ matrix. They choose its $n$ rows independently and uniformly from $\{0,1\}^m$. The columns are dissociated exactly when no nonzero ternary vector $s\in\{-1,0,1\}^m$ lies in the matrix kernel. If $s$ has $t$ nonzero coordinates, a random row is orthogonal to it with probability less than $(1.5t)^{-1/2}$. Summing the resulting failure probability over the sign and support types gives

$$\sum_{t=1}^m \binom mt 2^t(1.5t)^{-n/2}<1$$

when

$$n>(2\log_2 3+o(1))\frac{m}{\log_2 m}.$$

The union bound therefore produces the desired matrix; inverting this relation gives $m=(1+o(1))n\log_2n/\log_2 9$.

Theorem 2 uses the complementary ternary-span viewpoint. Maximality of a dissociated set $\Lambda\subseteq A$ implies

$$A\subseteq\operatorname{Span}_{\{-1,0,1\}}(\Lambda):$$

otherwise an element outside this span could be adjoined without creating a ternary relation. Hence every element of $M$ is a ternary combination of $\Lambda$. Every one of the $2^{|M|}$ distinct subset sums of $M$ is then an integer combination of $\Lambda$ with coefficients between $-|M|$ and $|M|$, so

$$2^{|M|}\leq(2|M|+1)^{|\Lambda|},$$

which gives the lower comparison. Reversing $M$ and $\Lambda$ gives $|\Lambda|\leq |M|\log_2(2|\Lambda|+1)$. The proof first uses the ternary span of $M$ to bound $|\Lambda|\leq(3^{|M|}-1)/2$, then substitutes successively into the symmetric inequality to obtain the displayed upper bound.

The comparison is sharp in order. The standard coordinate vectors form a maximal dissociated subset of $\{0,1\}^n$ of size $n$, while the set supplied by Theorem 1 can be extended to a maximal dissociated subset of size $\Omega(n\log n)$. Thus one and the same Boolean cube has maximal bases whose sizes differ by a logarithmic factor.

Relevance and limitation for Problem 963

Problem 963 asks whether every $N$-element set of reals contains a dissociated subset of size at least $\lfloor\log_2N\rfloor$. Theorem 1 instead constructs an unusually large dissociated subset inside the special ambient set $\{0,1\}^n$, which has $N=2^n$ elements. Choosing $n$ reals linearly independent over $\mathbb Q$ embeds $\mathbb Z^n$ additively into $\mathbb R$, so this construction can be realized as a special $N$-element real set while preserving dissociation. It is still an existence result for that set, not a lower bound uniform over all $N$-element real sets.

Theorem 2 likewise compares two maximal bases only after the ambient set has been fixed. It does not supply the size of either basis from $|A|$ alone. The ternary-span observation does give, for any maximal dissociated $\Lambda\subseteq A$,

$$|A|\leq 3^{|\Lambda|} \qquad\text{and hence}\qquad |\Lambda|\geq\log_3|A|,$$

but its three coefficient choices do not yield the requested base-$2$ bound. The comparison theorem cannot close that gap without an additional lower bound on a dissociated basis. Neither result therefore establishes the universal $\lfloor\log_2N\rfloor$ extraction asked about in E0963.

Read status: claims checked. The paper was read whole, the theorem statements were checked clause by clause against p. 2, and the proofs of Theorems 1 and 2 were traced through the displayed random-matrix and counting arguments. No proof was independently verified.

Bears on. #963: background only. Theorem 2 shows that two inclusion-maximal dissociated subsets of one finite set differ in size by at most a logarithmic factor, and Theorem 1 with the standard basis of $\{0,1\}^n$ shows that such a factor can occur; neither bounds the largest dissociated subset of an $N$-element real set from below in terms of $N$. The $\log_3|A|$ bound derived above from the paper's ternary-span remark (p. 1) is the corpus's deduction, Erdős's known bound, not a result of the paper. The paper does not address the problem's $\lfloor\log_2|A|\rfloor$ question.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.