2
$\begingroup$

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference.

b) all differences distinct.

c) differences all satisfy $t\leq d \leq D.$

Improve this question
$\endgroup$
5
  • $\begingroup$ I assume this will depend heavily on whether you assume all the progressions to share the same difference? $\endgroup$
    – Seva
    Commented Jul 5, 2018 at 9:30
  • 1
    $\begingroup$ A question I raised in a paper a few years back is whether there is any $n$ for which there is a partition of $\{\,1,2,\dots,n\,\}$ into arithmetic progressions, each of length at least 3, and no two with the same common difference. $\endgroup$
    – Gerry Myerson
    Commented Jul 5, 2018 at 9:36
  • $\begingroup$ @Gerry, maybe you are interested in higher order Langford sequences? There is a solution with triplets for n=27 available on the internet. Gerhard "Just A Short Search Away" Paseman, 2018.07.05. $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2018 at 6:50
  • $\begingroup$ Also, the nth Bell number is bounded by n! , and I suspect your quantity can be bounded by a fractional power of the nth Bell number. Gerhard "Chiming In With Tighter Bounds" Paseman, 2018.07.06. $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2018 at 7:11
  • $\begingroup$ @Gerhard, I see what you mean – dialectrix.com/langford.html explains higher order Langford sequences well. But the question I raised has an extra condition that I didn't mention. What I really want is a positive integer $n$, and a collection of congruences $x\equiv a_i\bmod{m_i}$, $m_i$ distinct, such that each number from $1$ to $n$ satisfies exactly one congruence, and each congruence is satisfied by at least $3$ of the numbers from $1$ to $n$. $\endgroup$
    – Gerry Myerson
    Commented Jul 6, 2018 at 9:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .