PreprintarXiv licencearXiv
Arithmetic Progressions in a Random Binary Subset-Sum Set
Abstract
Let u=(un)n≥0 be a binary sequence, and define X0=1, Xn+1=2Xn+un (n≥0). Let Au be the set of all nonempty finite subset sums of the sequence (Xn), and let Lu(N) denote the maximum length of an arithmetic progression contained in Au∩[1,N]. We prove that there are absolute constants c>0 and N0≥ 1 such that, for every binary sequence u, Lu(N)≥ exp (c√((log N)/(loglog N))) for all N≥ N0. Moreover, if the random variables un are independent and uniformly distributed on {0,1}, then, almost surely, Lu(N)≪u N2/3exp (C√(log Nloglog N)), where C>0 is an absolute constant. Furthermore, every eventually periodic binary sequence satisfies Lu(N)≫u N1/2.
Related
- Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings
- Triple divisor type functions in arithmetic progressions to prime power moduli
- Hitting Arithmetic Progressions at the Square-Root Scale
- Average twin prime conjecture for elliptic curves in arithmetic progressions
- Smooth numbers in simultaneous arithmetic progressions
BibTeX
@misc{hegyvari2026arithmetic,
title = {{Arithmetic Progressions in a Random Binary Subset-Sum Set}},
author = {Norbert Hegyvári and Thang Pham and Boqing Xue},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33067},
eprint = {2609.33067},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33067},
}
RIS
TY - UNPB
TI - Arithmetic Progressions in a Random Binary Subset-Sum Set
AU - Norbert Hegyvári
AU - Thang Pham
AU - Boqing Xue
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33067
UR - https://arxiv.org/abs/2609.33067
AB - Let u=(u_n)_n≥0 be a binary sequence, and define X_0=1, X_n+1=2X_n+u_n (n≥0). Let A_u be the set of all nonempty finite subset sums of the sequence (X_n), and let L_u(N) denote the maximum length of an arithmetic progression contained in A_u∩[1,N]. We prove that there are absolute constants c>0 and N_0≥ 1 such that, for every binary sequence u, L_u(N)≥ exp (c√((log N)/(loglog N))) for all N≥ N_0. Moreover, if the random variables u_n are independent and uniformly distributed on {0,1}, then, almost surely, L_u(N)≪_u N^2/3exp (C√(log Nloglog N)), where C>0 is an absolute constant. Furthermore, every eventually periodic binary sequence satisfies L_u(N)≫_u N^1/2.
ER -