Wiki
Wiki

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

Updated


Claim. Let A(n)A(n) be the greedy sequence of Problem 271, written S(0,n)S(0,n) in the paper's notation for Stanley sequences. Theorem 1.2 of D. Rolnick, On the classification of Stanley sequences, European J. Combin. 59 (2017), 51--70 (arXiv:1408.1940; result labels are those of the arXiv version), takes a positive integer kk, a monotone decreasing family A\mathcal A of subsets of {0,…,k−1}\{0,\ldots,k-1\} and the set AA of the sums ∑a∈B3a\sum_{a\in B}3^a over B∈AB\in\mathcal A, and proves that S(A∪{3k})S(A\cup\{3^k\}) and S(A∪{2⋅3k})S(A\cup\{2\cdot3^k\}) are independent Stanley sequences, with closed-form descriptions by ternary digits. The family {∅}\{\emptyset\} gives A={0}A=\{0\}, so the theorem proves the descriptions of A(3k)=S(0,3k)A(3^k)=S(0,3^k) and A(2⋅3k)=S(0,2⋅3k)A(2\cdot3^k)=S(0,2\cdot3^k) for every k≥1k\ge1 that Odlyzko and Stanley had stated without proof on their claim page; the paper proves the 3k3^k case in full and describes the 2⋅3k2\cdot3^k proof as very similar. An independent Stanley sequence is regular, and Corollary 2.9 (from Proposition 2.7, which gives a2j−σ=α3j+β2ja_{2^j-\sigma}=\alpha3^j+\beta2^j for large jj) proves that every regular Stanley sequence follows the first of the two growth patterns of Odlyzko and Stanley: ana_n lies between constant multiples of nlog⁡23n^{\log_23} for all large nn.

Covers. The values n=3kn=3^k and n=2⋅3kn=2\cdot3^k for k≥1k\ge1: the explicit description of the aka_k and their growth of order klog⁡23k^{\log_23}. Not covered: n=1n=1 and n=2n=2 (the case k=0k=0 is outside Theorem 1.2), every other nn, and the exact constants lim inf⁡ak/klog⁡23=1/2\liminf a_k/k^{\log_23}=1/2 and lim sup⁡ak/klog⁡23=1\limsup a_k/k^{\log_23}=1 of Odlyzko and Stanley's Remark 2.

Depends on. Nothing in this wiki: the proofs are the paper's own, and the memorandum's unproved statements are not an input.

Acceptance. Refereed: European Journal of Combinatorics 59 (2017), 51--70, the DOI linked above; the publication record dates the issue to January 2017, and the page is named by the first arXiv posting, 2014-08-08. Reviewed is not listed: the site labels the problem OPEN and its commentary does not mention the paper. Formalized is not listed: no Lean statement or proof of the result is recorded.