2
$\begingroup$

Given $\lambda>0$ let $B=B(\lambda)$ be the smallest integer such that there exist infinite integer sequences having values in $\lbrace 1,2,\ldots,B-1,B\rbrace$ and satisfying the following property: We have $\sum_{k=i+1}^{j-1}s_k>\lambda s_i$ whenever $i<j$ is such that $s_i=s_j$. (Otherwise stated, the sum of all coefficients strictly between two equal coefficients $a$ is strictly larger than $\lambda a$.)

Examples: For $\lambda=1$ the $4$-periodic sequence $1,2,1,3,1,2,1,3,\ldots$ works showing $B(1)\leq 3$ and it is easy to check that $B(1)>2$.

For $\lambda=2$ the $10$-periodic sequence with period $1,2,3,1,4,1,2,3,1,5$ works showing $B(2)\leq 5$.

An easy analysis of the greedy algorithm (which chooses each coefficient as small as possible) shows $B(\lambda)\leq 2\lambda+2$.

Experimentally, the greedy algorithm (which produces always an eventually periodic sequence) gives a bound which seems slightly larger than $\lambda$. It shows for example $B(100)\leq 109$. It produces however not necessarily the optimal bound.

Is the equality $B(\lambda)>\lambda$ true for all $\lambda$? (Equivalently, given an infinite sequence $s_1,s_2,\ldots$ with values in $\lbrace 1,\ldots,B\rbrace$, do there always exist integers $i<j$ such that $s_i=s_j$ and $\sum_{k=i+1}^{j-1}s_k\leq Bs_i$?)

Addendum: F. Petrov's nice answer shows $B(\lambda)>\lambda$. Numerical experiments suggest $B(\lambda)-\lambda<\sqrt{\lambda}$ if $\lambda$ is sufficiently large. This might be tricky to prove ($B(\lambda<2\lambda$ is easy but I guess getting something like $B(\lambda)<\lambda+\sqrt{\lambda}$ asymptotically needs good tools (Petrov suggests Lovasz's local lemma in a comment.)).

$\endgroup$

1 Answer 1

2
$\begingroup$

I think, yes, simply by averaging. Take a very long initial segment of your sequence, which contains $N_i$ items equal to $i$ for $i=1,\ldots,B$. Assume that the sum between consecutive $j$'s is at least $Bj+1$. Sum up over all $j=1,\ldots B$ and over all segments. You get the total sum at least $S:=\sum_{j=1}^B (N_j-1)(Bj+1)$. On the other hand, you count each element at most $B-1$ times. Thus $S\leqslant (B-1)\sum jN_j$ that is not correct if $\sum N_j$ is large.

$\endgroup$
2
  • $\begingroup$ This shows $B(\lambda)>\lambda$. My computer suggests that perhaps $\lim_{\lambda\rightarrow\infty}B(\lambda)/\lambda=1$. (I got $B(500)\leq 519$.) $\endgroup$ Commented Oct 22, 2023 at 18:44
  • $\begingroup$ I would try a random $N$-periodic sequence with probability of $j$ proportional to $1/j$, and try to apply some version of Lovász local lemma. $\endgroup$ Commented Oct 23, 2023 at 8:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .