Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a finite set of size . Is it true that, for any fixed , there are
many such that ?
If we further ask that (for any fixed ) then is the number of solutions
with the implied constant independent of and ?
Source: erdosproblems.com/362
An accepted solution exists. The statement is true.
PROVED (LEAN), on the site's label, which the two refereed sources support, one for each question. The derived frontmatter standing is solved, proved: the page lists the two questions as its parts, and each is settled by an accepted partial claim page, Sárközy and Szemerédi 1965 settling the first question and Halász 1977 the second, so the two claims together settle every part, and both questions are answered yes below. A Lean development that declares itself a formalization of both results is linked from both claim pages and described under Formalization; it was not built here and supplies no formalized evidence. First question: yes, by the Satz of Sárközy and Szemerédi (Acta Arith. 11 (1965), 205--208, refereed): for every and , any distinct positive reals have ; for the finitely many the trivial gives the bound with the constant (an authored line), so with an absolute constant. The order is sharp: has (the paper's remark), and Stanley's Corollary 5.1 (SIAM J. Algebraic Discrete Methods 1 (1980), 168--184, refereed) identifies the exact maximum over distinct positive reals as the middle coefficient of , attained by , and his Corollary 5.3 the maximum over all sets of distinct reals, attained by , the site's set. Second question: yes, by Halász's Theorem 2 and the remark that follows it (Period. Math. Hungar. 8 (1977), 197--211, refereed): for vectors with for such that, for some and every unit vector , at least of them satisfy , at most of the signed sums lie in any open unit ball, and the remark records "a conjecture of Erdős (oral communication), confirmed by Theorem 2: if , , i.e., if in the above result of Sárközi and Szemerédi the number of signs in is also fixed", the multidimensional theorem the site's commentary credits and its consequence. For the page, the subsets with and are the sign vectors whose sum is the point , and translating so that its middle element is , which leaves the fixed-size counts unchanged, supplies the condition on with for , so the count is at most with an absolute constant (an authored reduction, recorded under The second question below; is covered by the trivial bound ). The conjecture itself is Erdős's (1965, with the constant independent of the subset size, his , the page's ; 1973, display (8.8), with the constant independent of , , and the sequence). Halász's printed proof of Theorem 2 is a one-paragraph modification (p. 208) of his proof of the probabilistic Theorem 4, not checked here. The site's label agrees with the two refereed sources.