Wiki
Wiki

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

Updated


Source. Erdős (1945), closing discussion, printed pp. 901–902 (published scan). The paper states that the real case is easy. The full deduction follows.

Statement. Let N≥1N\ge1 and let x1,…,xNx_1,\ldots,x_N be real with ∣xi∣≥1|x_i|\ge1. For any w∈Cw\in\mathbb C, let QinQ_{\mathrm{in}} count the sign assignments with ∣Z−w∣<1|Z-w|<1 and let QbdQ_{\mathrm{bd}} count those with ∣Z−w∣=1|Z-w|=1, where Z=∑iεixiZ=\sum_i\varepsilon_i x_i. Then

Qin+12Qbd≤BN.Q_{\mathrm{in}}+\frac12Q_{\mathrm{bd}}\le B_N.

Proof. First suppose w=uw=u is real. By the half-open version of Theorem 1, each of the intervals [u−1,u+1)[u-1,u+1) and (u−1,u+1](u-1,u+1] contains at most BNB_N assignments. Averaging their counts gives weight one to each interior assignment and weight one half to each endpoint assignment. This is exactly Qin+12QbdQ_{\mathrm{in}}+\tfrac12Q_{\mathrm{bd}}.

Now write w=u+ivw=u+iv with v≠0v\ne0. Every signed sum ZZ is real. If ∣v∣>1|v|>1, no such sum satisfies ∣Z−w∣≤1|Z-w|\le1, and the assertion is immediate. If 0<∣v∣≤10<|v|\le1, all qualifying sums lie in

[u−1−v2,  u+1−v2].\left[u-\sqrt{1-v^2},\;u+\sqrt{1-v^2}\right].

This is a closed interval of length strictly less than two; at ∣v∣=1|v|=1 it is a singleton. It is contained in the open interval (u−1,u+1)(u-1,u+1), so its entire unweighted assignment count is at most BNB_N by Theorem 1. The weighted count is no larger. □\square

Scope. This proves the real-input assertion only. The corresponding complex-input statement is one of the paper's dated conjectures. The theorem is not a bound for the unweighted count in an arbitrary closed interval of length two.

Bears on. Problem 498: the real-input case of the weighted strengthening the paper proposes for the problem's bound.