Wiki
Wiki

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

Updated


This source concerns signed sums and families of subsets. Its published-page scan contains a GDZ archive cover, then printed pages 251–259 on PDF pages 2–10. The mathematical version is the 1965 journal article.

Finite set notation

Write B(S)\mathcal B(S) for all subsets of a finite set SS and Bn\mathcal B_n when ∣S∣=n|S|=n. In particular, B0={∅}\mathcal B_0=\{\varnothing\}. An antichain contains no two distinct comparable members.

A saturated symmetric chain in Bn\mathcal B_n contains one set at each rank k,k+1,…,n−kk,k+1,\ldots,n-k, for some 0≤k≤⌊n/2⌋0\le k\le\lfloor n/2\rfloor, with successive sets related by inclusion. Its length is its number of members, n−2k+1n-2k+1, rather than its number of edges. The source calls these subchains of maximal chains. Empty lists arising in the induction are discarded.

Set (nt)=0\binom nt=0 for integers tt outside 0≤t≤n0\le t\le n. For r≥1r\ge1, write

Bn(r)={(n⌊(n+r)/2⌋),1≤r≤n+1,0,r>n+1.B_n(r)= \begin{cases} \displaystyle\binom n{\lfloor(n+r)/2\rfloor},&1\le r\le n+1,\\ 0,&r>n+1. \end{cases}

These are the chain-tail counts proved at the remark after Lemma I. The number qq of antichains is a nonnegative integer. Its union is empty when q=0q=0; the bound by largest rank levels is truncated at n+1n+1. All subset-family bounds use ≤\le, permitting equality.

Signed sums and discs

For a1,…,an∈Ca_1,\ldots,a_n\in\mathbb C, the counted objects are sign choices ε∈{−1,1}n\varepsilon\in\{-1,1\}^n for which s(ε)=∑iεiais(\varepsilon)=\sum_i\varepsilon_i a_i lies in a region. Distinct choices giving the same complex number are counted separately. The unique empty choice at n=0n=0 has sum zero.

A closed unit disc is {z:∣z−c∣≤1}\{z:|z-c|\le1\}; an open unit disc is {z:∣z−c∣<1}\{z:|z-c|<1\}. The plane theorem uses ∣ai∣>1|a_i|>1 and allows a closed disc. The finite scaling consequence uses ∣ai∣≥1|a_i|\ge1 and requires an open disc. The norm-one closed-disc version is false.

Inputs and coverage

The plane chain proves Lemma I, the chain-count remark, Lemma II, Theorem II, Theorem I, and the open-disc transfer. It includes the binomial identity used by Theorem II and uses only finite induction, finite counting, and elementary Euclidean inner-product and rotation facts. Although the source attributes Lemma II to Erdős 1945, its proof is included locally and is not an unproved imported input.

The later higher-dimensional branch has only stated source claims and proof pointers here. No complete proof of its Lemmas III/IV or Theorem III is claimed.

Bears on. Problem 498, with the explicit disc and multiplicity conventions above.