On generalized Stanley sequences

DOI10.1007/S10474-018-0791-1MaRDI QIDQ1747975zbMATH OpenOpenAlexFDO

Authors Sándor Kiss, Csaba Sándor, Quan-Hui Yang

Publication date 27 April 2018

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.01939, http://real.mtak.hu/85705/1/On%20generalized%20Stanley%20sequences.pdf

zbMATH Keywords

AP\({}_k\)-covering sequencearithmetic progressionprobabilistic methodStanley sequence

Mathematics Subject Classification ID

Arithmetic progressions (11B25) Other combinatorial number theory (11B75)

Abstract: Let $mathbbN$ denote the set of all nonnegative integers. Let $kge3$ be an integer and $A_0=a_1,dots,a_t$ $(a_1<ldots<a_t)$ be a nonnegative set which does not contain an arithmetic progression of length $k$. We denote $A=a_1,a_2,dots$ defined by the following greedy algorithm: if $lget$ and $a_1,dots,a_l$ have already been defined, then $a_{l+1}$ is the smallest integer $a>a_l$ such that $a_1,dots,a_{l}cupa$ also does not contain a $k$-term arithmetic progression. This sequence $A$ is called the Stanley sequence of order $k$ generated by $A_0$. In this paper, we prove some results about various generalizations of the Stanley sequence.

Review text

A strictly increasing sequence \(A\) of non-negative integers is called an AP\({}_k\)-covering sequence, if there exists an \(n_0\), such that for all \(n>n_0\), number \(n\) and some \((k-1)\) terms of the sequence, each less then \(n\), make a \(k\)-term arithmetic progression. Let \(A(n)\) enumerate the number of terms of the sequence \(A\) up to \(n\). The paper proves that there exists an AP\({}_3\)-covering sequence \(A\) such that \(\liminf \frac{A(n)}{\sqrt{n}}\leq 2\) and that there exists an AP\({}_3\)-covering sequence \(A\) such that \(\limsup \frac{A(n)}{\sqrt{n}}\leq 36\). More general, they prove that there exists an AP\({}_k\)-covering sequence \(A\) such that \(A(n)=O((\log n)^{\frac{1}{k-1}} n^{\frac{k-2}{k-1}})\), where the constant in the big-Oh term may depend on \(k\). The paper poses the following conjectures: for any integer \(k \geq 3\), there exists an AP\({}_k\)-covering sequence \(A\) such that \(\limsup \frac{A(n)}{n^{{(k-2)}/{(k-1)}}}<\infty\), and for any integer \(k \geq 3\) there exists a positive constant \(c_k\), such that for any AP\({}_k\)-covering sequence \(A\), \(\liminf \frac{A(n)}{n^{{(k-2)}/{(k-1)}}}>c_k\).

Recommendations

• On \(\text{AP}_{3}\)-covering sequences
• A note on \(AP_3\)-covering sequences
• On the counting function of Stanley sequences
• On the growth of the counting function of Stanley sequences
• On the growth of Stanley sequences

Cites work

• Greedy algorithm, arithmetic progressions, subset sums and divisibility
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the counting function of Stanley sequences
• On the growth of the counting function of Stanley sequences
• Sets of Integers With No Long Arithmetic Progressions Generated by the Greedy Algorithm
• The probabilistic method

Cited in

(10)

• Stapled sequences and stapling coverings of natural numbers
• On \(\text{AP}_{3}\)-covering sequences
• Characters of independent Stanley sequences
• A note on \(AP_3\)-covering sequences
• On the growth of Stanley sequences
• Covering an arithmetic progression with geometric progressions and vice versa
• On the classification of Stanley sequences
• On the counting function of Stanley sequences
• Complete 3-term arithmetic progression free sets of small size in vector spaces and other abelian groups
• Novel structures in Stanley sequences

This page was built for publication: On generalized Stanley sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747975)