0
$\begingroup$

Given an integer $k\ge 1$ and a set $S$ of positive integers, let $$ p_{k,S}(n) $$ be the number of partitions of $n$ into $k$ not necessarily distinct summands from $S$ up to reordering. In other words, $p_{k,S}(n)$ is the number of vectors $x=(x_1,\ldots,x_k) \in S^k$ such that $x_1+\cdots+x_k=n$, $x_i \in S$ for all $i=1,\ldots,k$, where two vectors $x$ and $y$ are identified if $\{x_1,\ldots,x_k\}=\{y_1,\ldots,y_k\}$.

It is well-known that, if $S=\{1,\ldots,n\}$, then $$ p_{k,S}(n)\sim \frac{n^{k-1}}{k!(k-1)!} \quad \text{ as }n\to \infty. $$

Question. Fix a positive integer $m$. Is it true that there exists $c>0$ such that if $n$ is sufficiently large and $S\subseteq \{1,\ldots,n\}$ satisfies $S\cap [x,x+m]\neq \emptyset$ for all $x\le n$ and $\text{gcd}(S)=1$ then $$ p_{k,S}(n)\ge c n^{k-1} \,\,? $$

Improve this question
$\endgroup$
4
  • $\begingroup$ If $c=0.01$ and $S=\{1,\ldots,cn\}$, then $p_{k,S}(n)=0$ for all $k<100$. Similarly if $S=\{n-cn,\ldots,n\}$, then $p_{k,S}(n)=0$ for all $k>1$. I think you might need some more conditions. $\endgroup$ Commented Mar 25 at 23:02
  • $\begingroup$ @AnthonyQuas Thank you, I fixed the conditions on $S$ $\endgroup$ Commented Mar 25 at 23:17
  • $\begingroup$ You also need some condition to rule out situations like where all elements of $S$ are congruent modulo some $b$. $\endgroup$ Commented Mar 25 at 23:18
  • $\begingroup$ @AnthonyQuas Thank you again. The condition $\mathrm{gcd}(S)=1$ is the one usually given in partition results, but the answer below of user558300 shows that it is still not sufficient. This is fine $\endgroup$ Commented Mar 26 at 10:46

1 Answer 1

Reset to default
1
$\begingroup$

The statement is false.

Fix an integer $m \ge 1$ and set $d = m + 1 \ge 2$. Consider the case $k = 2$. We construct a sequence of integers $n \to \infty$ and corresponding sets $S_n \subseteq \{1, \dots, n\}$ satisfying the given conditions, yet having $p_{2,S_n}(n) = 0$.

For any integer $n$ such that $n \ge 1$ and $n \equiv 1 \pmod{d}$, define the set: $$S_n = \{ s \in \{1, \dots, n\} : s \equiv 1 \pmod{d} \}.$$

We can make $n$ arbitrarily large. By definition, $S_n \subseteq \{1, \dots, n\}$. Also, since $n \ge 1$ and $n \equiv 1 \pmod d$, we have $1 \in S_n$. Therefore, $\gcd(S_n) = 1$.

Now we have to show $S_n \cap [x, x+m] \neq \emptyset$ for every integer $x \in \{1, \dots, n\}$. Let $x \in \{1, \dots, n\}$. Let $s$ be the largest element of $S_n$ such that $s \le x$.

  • If $x=s$, then $s \in S_n \cap [x, x+m]$ since $m \ge 1$.

  • If $x > s$, let $s'$ be the successor of $s$ in $S_n$. Since $S_n$ consists of elements congruent to $1 \pmod d$, $s'$ exists if $s<n$, and $s' = s+d$. We have $s < x < s' = s+d$. Since $x \ge s+1$, we have $x+m \ge s+1+m = s+d = s'$. Thus, $s' \in (x, x+m]$. This implies $s' \in S_n \cap [x, x+m]$.

  • If $s=n$ (which implies $x=n$), then $n \in S_n \cap [n, n+m]$.

In all cases, the interval $[x, x+m]$ contains an element of $S_n$.

Now, consider the partition count $p_{2, S_n}(n)$. This is the number of multisets $\{x_1, x_2\}$ such that $$x_1 + x_2 = n, \quad \text{with } x_1, x_2 \in S_n.$$

Since every element $x_i \in S_n$ satisfies $x_i \equiv 1 \pmod{d}$, taking the equation modulo $d$ gives: $$n = x_1 + x_2 \equiv 1 + 1 \equiv 2 \pmod{d}.$$

However, we constructed $S_n$ for integers $n$ such that $n \equiv 1 \pmod{d}$. Combining these congruences gives: $$1 \equiv n \equiv 2 \pmod{d},$$

which implies $d \mid (2-1)$, so $d = 1$. This contradicts our definition $d = m + 1 \ge 2$.

Therefore, there are no solutions to the equation $x_1 + x_2 = n$ with $x_1, x_2 \in S_n$ and so $$p_{2,S_n}(n) = 0.$$

Since this holds for an infinite sequence of $n$ tending to infinity, the claim that $p_{k,S}(n) \ge c n^{k-1}$ for some $c>0$ and all sufficiently large $n$ cannot be true for $k = 2$.

Improve this answer
$\endgroup$

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.