On the equal sum partition problem
Shlomo Hoory and Dani Kotlar · 2026
Read On the equal sum partition problem by Shlomo Hoory and Dani Kotlar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06071.txt.
Introduction
Shlomo Hoory and Dani Kotlar map the boundary between solvable and unsolvable cases of the equal sum partition problem. Given set sizes in advance, can the numbers one through n be split into groups of those sizes so every group sums to the same total? A known slack condition is necessary, but past counterexamples show it is not sufficient.
The authors add infinite families of unsolvable cases that satisfy the slack condition across a wide range of ratios. They also give a new criterion for unsolvability. For the relaxed fractional version, they prove the slack condition is both necessary and sufficient. Building on that, they prove the problem is solvable for linear partitions when the condition holds strongly, using randomized rounding with tiny failure odds.
Catalog record
| CREATOR | Shlomo Hoory and Dani Kotlar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06071
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the equal sum partition problem Shlomo Hoory and Dani Kotlar Abstract . We consider the equal sum partition problem, motivated by distance magic graph labeling: Given n , k ∈ ℕ n,k\in\mathbb{N} such that k | ∑ i = 1 n i k\,|\sum_{i=1}^{n}i and a partition p 1 + ⋯ + p k = n p_{1}+\cdots+p_{k}=n , when is it possible to find a partition of the set { 1 , 2 , … , n } \{1,2,\ldots,n\} into k k subsets of sizes p 1 , … , p k p_{1},\dots,p_{k} , such that the element sum in each subset is the same? A known necessary condition is the slack condition , requiring that for all j j , placing the largest possible elements in the j j smallest sets yields a total sum that is at least what is needed. However, this condition is not sufficient, and known counterexamples exist. This work clarifies the boundary between solvable and unsolvable instances of the problem. We extend the list of unsolvable problem instances satisfying the slack condition by exhibiting infinite families where the n / k n/k ratio is any rational number in the interval ( 2 , 24 7 ) (2,\frac{24}{7}) , and a new criterion for unsolvability. Furthermore, we show that the slack condition is natural, as it is both necessary and sufficient for the fractional relaxation of the problem. Based on this result, we prove that the problem is solvable for the class of linear partitions, where k k is fixed, p 1 , … , p k p_{1},\ldots,p_{k} grow linearly with n n , and where the slack condition holds in a strong sense. We do this by applying a randomized rounding algorithm to a solution of the fractional relaxation of the problem and proving that the algorithm has an exponentially small failure probability. 1. Introduction 1.1. Background A distance magic labeling [ 12 ] (or sigma labeling [ 5 ] ) of a simple undirected graph with n vertices is a bijective assignment of the numbers in [n]=\{1,2,\ldots,n\} to its vertices, such that the sum of the values assigned to the neighbors of each vertex is the same. Challenges involving distance-magic labelings, such as deciding whether one exists, and constructing one when it does, are closely tied to questions about partitioning the set [n] . A classic example is the following: Given positive integers n and k with k dividing \sum_{i=1}^{n}i , can [n] be partitioned into k subsets whose element sums are all equal? Straight and Schillo [ 13 ] showed that the answer is yes. But what happens when the sizes of these subsets are prescribed? This is the subject of our work. Problem 1.1 ( [ 3 ] Problem 6.3 and [ 7 ] , Problem 1.1) . Let n,k and p_{1},\dots,p_{k} be positive integers such that p_{1}+\cdots+p_{k}=n and k divides \sum_{i=1}^{n}i . When is it possible to find a partition of the set [n] into k subsets of sizes p_{1},\dots,p_{k} , respectively, such that the sums of the elements in each subset are equal? Problem 1.1 was shown to be equivalent to problems of finding a distance magic labeling of complete multipartite graphs (Miller, Rodger and Simanjuntak [ 12 ] , Cichacz and Gőrlich [ 7 ] ), and of graphs obtained by replacing each vertex in C_{k} by a clique, with a slightly modified definition of distance magic labeling (Anholcer, Cichacz and Peterin [ 3 ] ). For more results and surveys on distance magic labeling, see [ 2 ] , [ 4 ] , and [ 9 ] . A clearly necessary condition for the existence of a partition as described in Problem 1.1 is that, for every j , if we place the largest available elements into the j smallest parts, the resulting total must be at least as large as the required sum, possibly with some additional “slack”. We refer to this requirement as the slack condition (see Definition 1.6 ). It was shown by Miller, Rodger and Simanjuntak [ 12 ] and Beena [ 5 ] that the slack condition is sufficient when k=2,3 . Kotlar [ 10 ] extended the result to k=4 and dared to conjecture (as did Arumugam, Froncek, Dalibor and Kamatchi [ 4 ] ) that this holds in general. However, Ebrahem Hoory and Kotlar [ 8 ] exhaustively checked all instances of Problem 1.1 with n\leq 200 , and identified two counterexample structures. Examples 2.8 and 2.9 illustrate these structures. In this paper, following the approach taken in two earlier works [ 10 , 8 ] , we study Problem 1.1 independently of the graph‑labeling questions related to it, as we think the problem is intrinsically interesting. 1.2. Definitions and notation For a positive integer n a composition of n is a sequence of positive integers P=[p_{1},p_{2},\ldots,p_{k}] such that \sum_{i=1}^{k}p_{i}=n . Given a composition of n so that k divides \sum_{i=1}^{n}i , we would like to know whether it is possible to find a partition of the set [n] into k subsets of sizes p_{1},\dots,p_{k} , respectively, such that the sum of the elements in each subset is the same. There is a necessary condition for this. To introduce it, we need some more definitions: Notation 1.2 . Given a composition [p_{1},p_{2},\ldots,p_{k}] of n , where k divides \sum_{i=1}^{n}i , we denote the target sum for partitioning [n] into k equal sum parts by s^{n,k}=\frac{n(n+1)}{2k}. Definition 1.3 . Let P=[p_{1},p_{2},\ldots,p_{k}] be a non-descending composition of a positive integer n . For j=1,\ldots,k let P_{j}=\sum_{i=1}^{j}p_{i} . For j=1,\ldots,k-1 let \textrm{slack}_{j}(P)=\sum_{i=1}^{P_{j}}(n-i+1)-js^{n,k}. We denote the slack of P by \textrm{slack}(P)=\min_{1\leq j<k}\textrm{slack}_{j}(P). Remark 1.4 . We do not include \textrm{slack}_{k}(P) in the minimum expression, as it is always 0. Observation 1.5 ( [ 3 ] ) . Let P=[p_{1},p_{2},\ldots,p_{k}] be a non-descending composition of a positive integer n . If it is possible to partition the set [n] into k equal-sum subsets of sizes p_{1},\dots,p_{k} , then \textrm{slack}(P)\geq 0 . Definition 1.6 . We call the condition {\textrm{s}lack}(P)\geq 0 the slack condition . If this condition holds for P , we say that P satisfies the slack condition. As satisfying the slack condition is a necessary condition for the existence of a partition of the set [n] into k equal-sum subsets of sizes given by P , we make it part of the definition: Definition 1.7 . A triple (n,k,P) is an instance of the Equal Sum Partition Problem (ESPP instance, for short), if n and k are positive integers such that k divides \frac{n(n+1)}{2} , and P=[p_{1},p_{2},\ldots,p_{k}] is a non-descending composition of n satisfying the slack condition. We say that an ESPP-instance (n,k,P) is solvable if it is possible to partition the set [n] into subsets of sizes p_{1},p_{2},\ldots,p_{k} respectively, so that the sum of the elements in each set is the same. Remark 1.8 . Since the composition P in an ESPP (n,k,P) contains the information about n and k , we shall sometimes use P instead of the triple (n,k,P) to refer to an ESPP instance. For example, we will say that P is solvable, meaning that the ESPP instance (n,k,P) is solvable. Notation 1.9 . Let (n,k,P) be an ESPP