pith. sign in

arxiv: 2605.06071 · v1 · submitted 2026-05-07 · 🧮 math.CO

On the Equal Sum Partition Problem

Shlomo Hoory , Dani Kotlar This is my paper

Pith reviewed 2026-05-08 08:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords equal sum partitionslack conditionfractional relaxationrandomized roundinglinear partitionspartition problemdistance magic labeling
0
0 comments X

The pith

The equal sum partition problem has solutions for linear partitions whenever the strong slack condition holds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines when the numbers from 1 to n can be divided into k groups of prescribed sizes p1 through pk so that every group has the same sum. A necessary slack condition on the sizes is already known, yet it fails to guarantee solutions in general, and the authors produce infinite families of counterexamples where the average group size n/k is a rational number strictly between 2 and 24/7. They prove that the same slack condition is both necessary and sufficient for a solution to exist in the fractional relaxation of the problem. For the special class of linear partitions, where k stays fixed while the pi grow linearly with n and the slack condition holds strongly, they show that a randomized rounding procedure applied to the fractional solution succeeds with exponentially small failure probability.

Core claim

The slack condition is necessary and sufficient for solvability of the fractional relaxation. For linear partitions with k fixed, subset sizes growing linearly in n, and the slack condition holding in a strong sense, a randomized rounding algorithm on the fractional solution produces an integer solution with exponentially small failure probability.

What carries the argument

Randomized rounding applied to a solution of the fractional relaxation under the strong slack condition.

If this is right

  • Infinite families of unsolvable instances exist that satisfy the slack condition, with n/k any rational in (2, 24/7).
  • The slack condition fully characterizes solvability of the fractional relaxation.
  • Linear partitions under the strong slack condition are always solvable.
  • The failure probability of the rounding procedure is exponentially small in n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same rounding technique might establish solvability for partitions whose sizes grow at other rates.
  • The new unsolvability criterion may help map additional boundary cases between solvable and unsolvable instances.
  • Because the problem arises from distance-magic graph labeling, these partition results may supply constructions for such labelings when the parameters are linear.

Load-bearing premise

The fractional relaxation admits a solution exactly when the strong slack condition holds, and the probabilistic analysis of rounding succeeds without further hidden dependence on the precise linear growth rates.

What would settle it

An explicit linear partition satisfying the strong slack condition for which no integer solution exists, or a concrete instance in which the failure probability of rounding is only polynomially small.

Figures

Figures reproduced from arXiv: 2605.06071 by Dani Kotlar, Shlomo Hoory.

Figure 1
Figure 1. Figure 1: Satisfiability regions for a = 2.3 and a = 3.2. The two vertical black lines and the horizontal black line are respectively (2.5), (2.6) and (2.3). The upper bound (2.7) for v is the green curve, and the lower bound (2.15) is the orange line. As we show in Lemma 2.17, these two lines intersect at two points (u1, v1) and (u2, v2) where u1 is on the right vertical line. Thus, the primary region S1 is the pin… view at source ↗
read the original abstract

We consider the equal sum partition problem, motivated by distance magic graph labeling: Given $n,k \in \N$ such that $k\, | \sum_{i=1}^ni$ and a partition $p_1+\cdots+p_k=n$, when is it possible to find a partition of the set $\{1,2,\ldots,n\}$ into $k$ subsets of sizes $p_1,\dots,p_k$, such that the element sum in each subset is the same? A known necessary condition is the \emph{slack condition}, requiring that for all $j$, placing the largest possible elements in the $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$ ratio is any rational number in the interval $(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$ is fixed, $p_1,\ldots,p_k$ grow linearly with $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript studies the equal sum partition problem: given n and k with k dividing the triangular number, and a size partition p1 + ... + pk = n, decide when {1, ..., n} can be partitioned into k subsets of those sizes whose element sums are identical. It proves that the classical slack condition is necessary and sufficient for feasibility of the natural LP relaxation. It exhibits infinite families of slack-satisfying but unsolvable instances for every rational n/k in (2, 24/7) together with a new unsolvability criterion. For the linear-partition regime (k fixed, each pi linear in n) under a quantitatively strengthened slack hypothesis, it shows that a randomized-rounding algorithm applied to an optimal fractional solution succeeds with exponentially small failure probability.

Significance. The work sharpens the boundary between solvable and unsolvable instances of a natural partition problem with applications to distance-magic labelings. The LP equivalence supplies a clean structural fact that directly enables the probabilistic argument; the construction of infinite counterexample families is explicit and uniform over a positive-length interval of densities; and the rounding result supplies a constructive, high-probability algorithm in the linear-growth regime. These contributions are proportionate to the scope of the paper and rest on standard yet carefully applied tools of the field.

major comments (1)
  1. [Linear-partition theorem (likely §4 or §5)] The abstract states that the ordinary slack condition is necessary and sufficient for LP feasibility, yet the positive result invokes a 'strong sense' version of slack for the linear regime. The manuscript must explicitly define the strengthened condition (presumably in the section introducing the linear-partition theorem) and prove that it is implied by the ordinary slack plus the linear-growth hypothesis; otherwise the reduction from the LP solution to an integral solution with exponential tails is not fully justified.
minor comments (2)
  1. [Abstract] The abstract claims an 'exponentially small failure probability' but does not indicate the dependence on the linear coefficients or the slack margin; a brief statement of the Chernoff or martingale tail bound (with explicit constants) would make the claim self-contained.
  2. [Abstract] The interval (2, 24/7) for the new counterexample families is stated without clarifying whether the endpoints are attained or whether the families exist for every rational in the open interval; a single clarifying sentence would remove ambiguity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive suggestion regarding the linear-partition theorem. We address the single major comment below.

read point-by-point responses

  1. Referee: [Linear-partition theorem (likely §4 or §5)] The abstract states that the ordinary slack condition is necessary and sufficient for LP feasibility, yet the positive result invokes a 'strong sense' version of slack for the linear regime. The manuscript must explicitly define the strengthened condition (presumably in the section introducing the linear-partition theorem) and prove that it is implied by the ordinary slack plus the linear-growth hypothesis; otherwise the reduction from the LP solution to an integral solution with exponential tails is not fully justified.

    Authors: We agree that the strengthened slack condition invoked for the linear-partition regime must be defined explicitly and shown to follow from the ordinary slack condition together with the linear-growth hypothesis on the part sizes. In the revised manuscript we will insert a precise definition of the strong slack condition at the beginning of the section containing the linear-partition theorem. We will also add a short lemma establishing that, when k is fixed and each p_i grows linearly with n, the ordinary slack condition already implies the strong version; this lemma will immediately precede the randomized-rounding argument and thereby justify the exponential tail bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper first proves directly that the slack condition is necessary and sufficient for feasibility of the fractional LP relaxation. It then restricts to the linear-partition case (fixed k, linear growth of p_i) under a strengthened slack hypothesis and invokes standard randomized rounding whose exponential tail bounds follow from Chernoff or martingale concentration once the per-set margin is linear in n. No equation reduces the existence claim to a fitted parameter, no load-bearing step depends on a self-citation chain, and the rounding argument uses only generic probabilistic-method tools independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the equivalence of the slack condition with feasibility of the fractional relaxation (proved in the paper) and on standard concentration bounds for randomized rounding; no free parameters or invented entities are introduced.

axioms (2)
  • standard math The total sum 1+...+n is divisible by k whenever the equal-sum condition is considered.
    Invoked at the outset to make the target sum well-defined.
  • domain assumption Existence of a feasible solution to the fractional relaxation when the slack condition holds strongly.
    Used as the starting point for the randomized-rounding step in the linear-partition case.

pith-pipeline@v0.9.0 · 5594 in / 1442 out tokens · 47193 ms · 2026-05-08T08:24:00.835643+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references

  1. [1]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. Wiley-Interscience, Hoboken, NJ, 3rd edition, 2008

    2008

  2. [2]

    Anholcer, S

    M. Anholcer, S. Cichacz, and I. Peterin. Spectra of graphs and closed distance magic labelings.Discrete mathematics, 339(7):1915– 1923, 2016

    1915

  3. [3]

    Anholcer, S

    M. Anholcer, S. Cichacz, I. Peterin, and A. Tepeh. Distance magic labeling and two products of graphs.Graphs and Combinatorics, 31:1125–1136, 2015

    2015

  4. [4]

    Arumugam, D

    S. Arumugam, D. Froncek, and N. Kamatchi. Distance magic graphs-a survey.Journal of the Indonesian Mathematical Society, pages 11–26, 2011

    2011

  5. [5]

    S. Beena. On P and P′ labelled graphs.Discrete Mathematics, 309(6):1783–1787, 2009

    2009

  6. [6]

    Chen, H.-L

    F.-L. Chen, H.-L. Fu, Y. Wang, and J. Zhou. Partition of a set of integers into subsets with prescribed sums.Taiwanese Journal of Mathematics, 9(4):629–638, 2005

    2005

  7. [7]

    Cichacz and A

    S. Cichacz and A. G˝ orlich. Constant sum partition of sets of integers and distance magic graphs.Discussiones Mathematicae Graph Theory, 38(1):97–106, 2018. 26 ON THE EQUAL SUM PARTITION PROBLEM

    2018

  8. [8]

    Ebrahem, S

    E. Ebrahem, S. Hoory, and D. Kotlar. An infinite family of counterexamples to a conjecture on distance magic labeling.Experimental Mathematics, pages 1–13, 2024

    2024

  9. [9]

    J. A. Gallian. A dynamic survey of graph labeling.Electronic Journal of combinatorics, 1(DynamicSurveys):DS6, 2018

    2018

  10. [10]

    D. Kotlar. Distance magic labeling in complete 4-partite graphs.Graphs and Combinatorics, 32:1027–1038, 2016

    2016

  11. [11]

    A. W. Marshall, I. Olkin, and B. C. Arnold.Inequalities: theory of majorization and its applications. Springer, 1979

    1979

  12. [12]

    Miller, C

    M. Miller, C. Rodger, and R. Simanjuntak. Distance magic labelings of graphs.Australian journal of combinatorics, 28:305–315, 2003

    2003

  13. [13]

    H. J. Straight and P. Schillo. On the problem of partitioning{1, 2,..., n}into subsets having equal sums.Proceedings of the American Mathematical Society, 74(2):229–231, 1979

    1979

  14. [14]

    W. L. Winston.Operations research: applications and algorithm. Thomson Learning, Inc., 2004. ON THE EQUAL SUM PARTITION PROBLEM 27 AppendixA.Iterative algorithm for solving the fluid mixing problem Algorithm 3Iterative Solution For The Fluid Mixing Problem Input:A fluid mixing problemπ= ( a, u, b, v) withnsource containers andktarget containers with slack...

    2004