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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.