# $p$-Splittable Integers

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.

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

• 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? – pjs36 Dec 5 '15 at 19:48
• Yes, there is a 25-character limit. – Batominovski Dec 5 '15 at 19:48
• 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 :-) – Jyrki Lahtonen Dec 8 '15 at 7:45
• 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. – Batominovski Dec 8 '15 at 7:53
• Ok. I believe you! – Jyrki Lahtonen Dec 8 '15 at 7:53

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.

• Bounty award goes to you due to your significant attempt, despite the incomplete answer. – Batominovski Dec 15 '15 at 21:09
• 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$ – Batominovski Dec 15 '15 at 21:11
• 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? – obstkuchen Dec 15 '15 at 22:55