12
$\begingroup$

This question Sudokus with no 3-term arithmetic progressions within made me wonder about the following question.

What is the longest sequence composed of the integers 1..N (or 0..N-1 if you have a programmer mind) such that no subsequence of 3 numbers forms an arithmetic progression?

The sequence must include all integers in the range exactly once each.

In other words, find the largest N such that you can arrange integers 1..N in a way to avoid including an arithmetic progression anywhere as an (ordered) subset of 3 of the numbers.

Improve this question
$\endgroup$
2
  • $\begingroup$ Does this include out-of order sequences as well, e.g., 4, 8, 6? $\endgroup$
    – Someone
    Commented Jan 12 at 13:20
  • $\begingroup$ No. It only applies to any subset of 3 numbers but keeping the order. Anyway, you need to include all integers. $\endgroup$
    – Florian F
    Commented Jan 12 at 13:28

2 Answers 2

Reset to default
12
$\begingroup$

In the comments here https://mathoverflow.net/questions/375602/analogue-to-szemer%C3%A9dis-theorem-for-non-monotone-sequences I find the following construction:

Consider all the at-most-k-bit binary numbers. Write them down in the usual order, then reverse all their bits; so e.g. if k=5 then in position 13 instead of 01101 we have 10110 or (in decimal) 22.

This sequence contains no length-3 arithmetic progression! Suppose it does, so we have $a < b < c$ with $r_k(a)+r_k(c) = 2r_k(b)$ where $r_k(\dots)$ is the bit-reversing function for length-at-most-$k$ binary numbers. And suppose we've done this for the smallest possible $k$. Then obviously our numbers don't all have the same "top bit" (else we could delete it and reduce $k$ by one). This means that $a,c$ have different "top bits", which means that their reversals have different 0th-bits, which means that the sum of their reversals is odd, contradiction.

Hence there is no longest such sequence: we can find AP-free sequences as long as we please.

(If we impose the requirement that the sequences be increasing, there's a well known paper by Erdős and Turan in 1936 that asks essentially this question -- more precisely, they ask: for given N, how long can the sequence be? -- and proves a few things; the main conjecture made there wasn't proved until 1975 and another stronger conjecture E&T made later eventually turned out to be false; so questions about this sort of thing can be very tough.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Congrats, that was the expected answer. $\endgroup$
    – Florian F
    Commented Jan 12 at 20:39
11
$\begingroup$

Another way to construct arbitrarily large sequences with the property:

A small example is easily constructed (The sequence "1" will do). Given a permutation of 1,2,...,n without an arithmetic 3-subsequence the same permutation of 1,3,..,2n-1 and of 2,4,...,2n also has no arithmetic 3-subsequence. Neither has their concatenation. Indeed, any 3-subsequence either lies entirely in one half or has an odd first and an even last element.

Note that as @Gareth points out if we start with 1 and repeatedly apply this doubling step we recover their sequence (shifted by one).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Isn't this in fact the same construction as the one in my answer? At least if you do the obvious thing and start with n=1 and iterate. All the numbers are 1 greater than in my answer, but otherwise I think it's the same. $\endgroup$
    – Gareth McCaughan ♦
    Commented Jan 12 at 18:36
  • $\begingroup$ @GarethMcCaughan Now that you mention it, yes, it would appear to be. If by construction you mean the outcome, not the process. Yours would be the "closed form" to my "recursion". The recursive method allows for some modifications that I think would be difficult to achieve with the closed form, for example, you could at any step swap the order of the two halves or use two different predecessors or flip either predecessor left-right or upside-down. Not that that would be of any value for the question as stated... $\endgroup$
    – Albert.Lang
    Commented Jan 12 at 19:18
  • $\begingroup$ This answer is equally good imho, essentially the same result but a different approach. $\endgroup$
    – Florian F
    Commented Jan 12 at 20:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.