12
$\begingroup$

Let $p$ be a positive integer. For each nonnegative integer $k$, write $[k]$ for the set $\{0,1,2,\ldots,k\}$. Also, we define $[-1]:=\emptyset$. We say that an integer $k\geq -1$ is $p$-splittable if there is a partition of $[k]$ into $p$ subsets $A_1$, $A_2$, $\ldots$, $A_p$ such that $\sum_{x\in A_1}\,x=\sum_{x\in A_2}\,x=\ldots=\sum_{x\in A_p}\,x$ (i.e., these sets have the same sum). Such a partition $\left\{A_1,A_2,\ldots,A_p\right\}$ is called a $p$-splitting of $[k]$.

What are all $p$-splittable integers for a given $p$? How many $p$-splittings of $[k]$ are there for each of these available $k$'s? If the exact number of $p$-splittings of $[k]$ is not easily computable, then what is the asymptotic answer?

Clearly, $k=-1$ and $k=0$ are $p$-splittable. We can also ignore the trivial case $p=1$. We know that, if $p=2$, then all $p$-splittable numbers are of the forms $4t-1$ and $4t$, where $t$ is a nonnegative integer. If $p$ is an odd prime, then all $p$-splittable numbers are integers of the forms $tp-1$ and $tp$, where $t\in\{0,2,3,4,\ldots\}$.

For $p=2$, we can show that the number of $2$-splittings of a $2$-splittable integer $k$ is given by the coefficient of $x^{\frac{k(k+1)}{4}}$ in the expansion of $\prod_{r=1}^k\,\left(1+x^r\right)$. For example, if $k=3$, there are two $2$-splittings of $[3]$, namely, $\big\{\{0,1,2\},\{3\}\big\}$ and $\big\{\{1,2\},\{0,3\}\big\}$, whereas $$\prod_{r=1}^3\,\left(1+x^r\right)=1+x+x^2+2x^3+x^4+x^5+x^6$$ whose coefficient of $x^{\frac{k(k+1)}{4}}=x^3$ is also $2$. Similarly, there are $2$, $8$, and $14$ $2$-spittings of $[k]$ for $k=4$, $k=7$, and $k=8$, respectively. I do not know if there is any closed form for this coefficient for an arbitrary $2$-splittable $k$.

I conjecture the following:

(1) If $p$ is odd, then, for any $j\in\{-1,0,1,2,\ldots,p-2\}$ such that $p\mid j(j+1)$, every integer of the form $tp+j$, where $t\in\{2,3,4,\ldots\}$, is $p$-splittable, and nothing else (except $-1$ and $0$) is $p$-splittable.

(2) If $p$ is even, then, for any $j\in\{-1,0,1,2,\ldots,2p-2\}$ such that $2p\mid j(j+1)$, every integer of the form $2tp+j$, where $t$ is a positive integer, is $p$-splittable, and nothing else (except $-1$ and $0$) is $p$-splittable.

This conjecture is true, at least, if $p$ is a prime power (where $j=-1$ and $j=0$ are the only possible choices of $j$). If you can show that (1) holds for $t=2$ and for $t=3$, and that (2) holds for $t=1$, then you are done. It is worth noting that, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable.

Inspiration: Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums

P.S. I include $k=0$ and $k=-1$ for the sake of completeness. There is nothing subtle about these numbers.

$\endgroup$
6
  • $\begingroup$ Just curious, but is there a reason you went for combi-number-theory rather than combinatorial-number-theory? Is the latter tag not allowed by the system due to its length? $\endgroup$ – pjs36 Dec 5 '15 at 19:48
  • 2
    $\begingroup$ Yes, there is a 25-character limit. $\endgroup$ – Batominovski Dec 5 '15 at 19:48
  • $\begingroup$ Would arithmetic-combinatorics work better as a tag, or does that have a different flavor to it? Admittedly I don't really know how that area defines itself - just asking :-) $\endgroup$ – Jyrki Lahtonen Dec 8 '15 at 7:45
  • $\begingroup$ I don't feel like this is an arithmetic combinatorics problem, if my understanding of arithmetic combinatorics is not far off. I could be wrong. $\endgroup$ – Batominovski Dec 8 '15 at 7:53
  • $\begingroup$ Ok. I believe you! $\endgroup$ – Jyrki Lahtonen Dec 8 '15 at 7:53
3
+100
$\begingroup$

likely last edit, formatting for clarity:

We say $n$ is $p$-splittable if there is a partition $A_1,...,A_p$ of $\{1,...,n\}$ with $\sum A_i := \sum_{a \in A_i} a = \sum A_j$ for all $i,j\leq p$

We call $n$ uniformly $p$-splittable if there is such a partition with $|A_i|=|A_j|$ for all $i,j \leq p$

We call such a partition a $p$-split of $n$

Let $s_p(n)$ $(\bar{s}_p(n))$ denote the number of (uniform) $p$-splits of $n$


Some truths:

$\bar{s}_p \leq s_p$

If $n$ is $p$-splittable then $p| \frac{(n+1)n}{2}$

If we have equality $s_p(n)=1$ (there is exactly one $p$-split of $n$)

$2p$ and $2p-1$ are $p$-splittable, $2p$ uniformly.

If $n$ is $p$-splittabe and $p'|p$ then $n$ is $p'$-splittable and we obtain a lower bound of $s_{p'}(n)\geq \frac {p!}{(\frac{p}{p'}!)^{p'}}$ (the number of ways to make a $p$-split into a $p'$-split by melting groups of $\frac{p}{p'}$ together)

(it may be possible to get a bound in terms of $s_p(n)$ if one can argue away double counting)

If $n$ is uniformly $p$-splittable then $mn$ is uniformly $p$-splittable for all m$\in \mathbb{N}$

If $n$ is $p$-splittable and $k$ is uniformly $p$-splittable, then $m+k$ is $p$-splittable

If $m,n$ are uniformly $p$-splittable then $m+n$ is uniformly $p$-splittable


The $p$-splittable numbers are then a finite union of (affine) copies of the uniformly $p$-splittables and are generated by finitely many primitive $p$-splittable numbers, a trivial upper bound on the count of primitives is the smallest non-zero uniformably $p$-splittable number $2p$. A better bound is achieved by $\# \{j \in \{-1,0,...,2p-2\} \; with \; 2p|j(j+1)\}$

It is conjectured this bound is exact and the primitive $p$-splittables are of the form $2p+j$ for $j$ in this set. (This is numerically proven for $p\leq 184$)

If $n$ is uniformly $p$-splittable then $n$ must be a multiple of $p$. I will give a full categorization:

Let $p \in \mathbb{N}$ then the uniformly $p$-splittables are $p \mathbb{N} \backslash p$ if $p$ is odd and $2p \mathbb{N}$ if p is even (or $\mathbb{N}$ for $p=1$)

proof: It is apparent that $2p$ is uniformly $p$-splittable and $p$ is not. It suffices to show that for odd $p$ $3p$ is uniformly $p$-splittable and for even $p$ no odd multiple is.

Let $p$ be even and $k$ odd. Then $\frac{kp(kp+1)}{2}$ is no multiple of $p$ (it is a odd multiple of $\frac p 2$)

Let $p$ be odd:

let $[i]$ denote $ i \; mod \; p$

Then a uniform $p$-split of $3p$ is given by $A_i = \{ 1+[i], (p+1)+[\frac{p-1}{2}+i], 2p+1+[p-1-2i]\}$ for $i=0,...,p-1$ Obviously each $A_i$ has 3 elements and each number $\leq 3p$ is represented. We need to show $[i]+[\frac{p-1}{2}+i]+[p-1-2i]$ is independent of $i$.

This is true because for $i \leq (p-1)/2$ all the arguments are in $(0,...,p-1)$ and for $(p+1)/2 \leq i \leq p-1$ we have $[\frac{p-1}{2}+i]=\frac{p-1}{2}+i-p$, $[p-1-2i]=p-1-2i+p$ in each case the sum is equal to $\frac{3(p-1)}{2}\square$

$\bar{s}_p(p^2) \geq (p-1)!$ (by construction of $(p-1)!$ uniform $p²$-splits)


Things to look into:

  • The original conjecture. It can be achieved by

    1. simply constructing $p$-splits for $2p+j$ for the given $j$ (note $j=-1,0$ are trivial) or

    2. Constructing an algorithm for it. Problems here lie in proving the algorithm finishes, this leads into study of finding how to split a set into heaps of (differing) given sizes (splits would be the special case where all stacks have equal size)

    3. Note that the requirement on $j$ is equivalent to $j \equiv -1$ or $ 0 \mod p_i$ for all prime powers $p_i|p$ (note this proves the conjecture for prime $p$ after giving a split for $3p-1$ ($p$ odd) like here)

  • Said study of "fitting" a set into a given tuple of integers $(d_1,...,d_n)$ (ie finding a partition with $\sum A_i = d_i$) Here the sets of the form $\{1,...,n\}$ are of a special importance for proving things about splittability

  • Study of splittability for sets $A\subset \mathbb{N} \neq \{1,...,n\}$

  • Study of $s_p$ and/or $\bar{s}_p$, I didn't look into the number of splits except when a bound just fell out of a proof.

$\endgroup$
3
  • $\begingroup$ Bounty award goes to you due to your significant attempt, despite the incomplete answer. $\endgroup$ – Batominovski Dec 15 '15 at 21:09
  • $\begingroup$ My critique would be that the work needs cleaning up. For example, by $2pN\setminus p$ for odd $p$, I think you meant $p\mathbb{N}\setminus\{p\}$. Also, $\mod{}$ (with TeX command \mod) and $\lim$ (with TeX command \lim) are better than $mod$ and $lim$ $\endgroup$ – Batominovski Dec 15 '15 at 21:11
  • $\begingroup$ I'll likely do some major reformatting tomorrow and may or may not put this to rest depending on whether i make any progress on the current working conjecture of "if n>2p and there is a p-split of n+2p then for every partition of $\{n+1,...,n+2p\}$ into p sets of size two there is a p-split of n+2p over that partition. (currently backed by numerical evidence for n=5, p=3 and by the requirement becoming weaker the bigger n becomes wrt p) proving that would essentially reduce the initial conjecture to calculating out all the n with p<n<3p (most of them are trivial because 2p|n(n+1)) any ideas? $\endgroup$ – obstkuchen Dec 15 '15 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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