pith. sign in

arxiv: 2303.07149 · v1 · submitted 2023-03-13 · 🧮 math.CO · math.NT

A Combinatorial Approach to Frobenius Numbers of Some Special Sequences (Complete Version)

Feihu Liu , Guoce Xin This is my paper

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

classification 🧮 math.CO math.NT
keywords Frobenius numbernumerical semigroupoptimization problemMacMahon's partition analysisSylvester numberSylvester sumcombinatorial approachspecial sequences
0
0 comments X

The pith

Transforming the Frobenius membership problem into an optimization task produces explicit formulas for the Frobenius number on special sequences.

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

The paper seeks to simplify the Frobenius problem by recasting it as an optimization task whose solution directly gives the largest non-representable integer. If that optimization admits an explicit answer, then a closed formula for g(A) follows at once. The authors apply the method to recover known formulas and derive new ones for particular sequences of integers. They further show that MacMahon's partition analysis, combined with a rational-function encoding of a polynomial tied to A, computes the Sylvester number n(A) and sum s(A). A sympathetic reader would care because the Frobenius number is hard to compute in general, so any reduction that works for infinite families is useful.

Core claim

The central discovery is that the question of which integers belong to the numerical semigroup generated by A can be replaced by an equivalent optimization problem; an explicit optimum then yields the Frobenius number g(A) without further correction. The same transformation, together with MacMahon's partition analysis on a rational function determined by A, supplies formulas for the number n(A) of non-representable integers and their sum s(A).

What carries the argument

The exact reduction of the semigroup membership question to a concrete optimization problem whose variables are the coefficients in the linear combination.

Load-bearing premise

The transformation from non-membership in the semigroup to the stated optimization problem is exact, so that the optimum directly identifies the Frobenius number with no extra terms needed.

What would settle it

A concrete sequence A for which the explicit optimum of the transformed problem differs from the independently computed Frobenius number g(A).

read the original abstract

Let $A=(a_1, a_2, ..., a_n)$ be relative prime positive integers with $a_i\geq 2$. The Frobenius number $g(A)$ is the greatest integer not belonging to the set $\big\{ \sum_{i=1}^na_ix_i\ |x_i\in \mathbb{N}\big\}$. The general Frobenius problem includes the determination of $g(A)$ and the related Sylvester number $n(A)$ and Sylvester sum $s(A)$. We present a new approach to the Frobenius problem. Basically, we transform the problem into an easier optimization problem. If the new problem can be solved explicitly, then we will be able to obtain a formula of $g(A)$. We illustrate the idea by giving concise proof of some existing formulas and finding some interesting new formulas of $g(A), n(A), s(A)$. Moreover, we find that MacMahon's partition analysis applies to give a new way of calculating $n(A), s(A)$ by using a rational function representation of a polynomial determined by $A$.

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

2 major / 1 minor

Summary. The paper claims that the Frobenius problem for coprime integers A can be transformed into an optimization problem whose explicit solution yields a formula for g(A); the same approach combined with MacMahon's partition analysis is asserted to produce formulas for the Sylvester number n(A) and sum s(A). It illustrates the method by supplying concise proofs of known formulas and deriving new ones for special sequences.

Significance. If the claimed transformation is exactly equivalent to the semigroup membership problem (bijective, with no hidden correction terms), the method would supply a direct combinatorial route to closed-form expressions for g(A), n(A), and s(A) on selected sequences, complementing existing algebraic techniques. The explicit use of partition analysis for the auxiliary invariants is a concrete strength that could be reusable.

major comments (2)
  1. [Abstract and the section introducing the transformation] The central claim rests on an unverified equivalence: the manuscript asserts that the optimization problem is obtained by a direct transformation whose optimum equals g(A), but supplies neither the explicit optimization formulation nor a general argument that every non-representable integer maps to a feasible point whose value is exactly the Frobenius number (and conversely). This equivalence is load-bearing for every derived formula.
  2. [The optimization reformulation] Without an explicit statement of the objective function and feasible set, it is impossible to confirm that the reduction preserves the extremal value for the sequences treated; any mismatch (omitted boundary cases or an objective differing from the indicator of non-membership) would require correction terms not mentioned in the claims.
minor comments (1)
  1. [Abstract] Notation for the numerical semigroup and the optimization variables should be introduced once and used consistently; the abstract uses both x_i and later unspecified variables.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying the need for greater explicitness in the central transformation. We agree that the equivalence between the Frobenius problem and the optimization formulation must be stated rigorously with an explicit objective function and feasible set. The revised manuscript will incorporate these clarifications.

read point-by-point responses

  1. Referee: [Abstract and the section introducing the transformation] The central claim rests on an unverified equivalence: the manuscript asserts that the optimization problem is obtained by a direct transformation whose optimum equals g(A), but supplies neither the explicit optimization formulation nor a general argument that every non-representable integer maps to a feasible point whose value is exactly the Frobenius number (and conversely). This equivalence is load-bearing for every derived formula.

    Authors: We accept this criticism. The current manuscript introduces the transformation conceptually but does not supply the explicit optimization problem (objective and constraints) nor a general bijective proof that the optimum equals g(A). In the revision we will add a dedicated subsection that states the precise optimization formulation and provides a direct argument mapping non-representable integers to feasible points whose values attain g(A), with the converse also shown. revision: yes

  2. Referee: [The optimization reformulation] Without an explicit statement of the objective function and feasible set, it is impossible to confirm that the reduction preserves the extremal value for the sequences treated; any mismatch (omitted boundary cases or an objective differing from the indicator of non-membership) would require correction terms not mentioned in the claims.

    Authors: We agree that the absence of the explicit formulation prevents verification. The revision will define the objective function and feasible set in full generality, verify that the reduction is exact (no omitted boundary cases or differing objectives) for the sequences treated, and confirm that no correction terms arise. This will be done before deriving the formulas for g(A), n(A), and s(A). revision: yes

Circularity Check

0 steps flagged

No circularity: direct transformation to optimization yields independent formulas

full rationale

The paper presents a combinatorial transformation of the Frobenius membership problem into an optimization problem whose explicit solution is asserted to supply g(A), n(A), and s(A) for special sequences. No equations or definitions in the abstract or described approach reduce the output formulas back to fitted parameters, self-referential quantities, or self-citation chains; the claimed equivalence is treated as a bijective reformulation whose explicit optima directly give the results without correction terms. This is a standard first-principles combinatorial method with no load-bearing self-referential steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definition of the numerical semigroup generated by coprime integers and on the existence of an optimization problem whose solution equals the Frobenius number; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption A = (a1,...,an) consists of relatively prime positive integers each at least 2.
    This is the classical setup for the Frobenius problem stated in the abstract.

pith-pipeline@v0.9.0 · 5719 in / 1252 out tokens · 23239 ms · 2026-05-24T10:00:30.831047+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On quotients of numerical semigroups for almost arithmetic progressions

    math.NT 2023-12 unverdicted novelty 5.0

    Reduces Apéry set of semigroup quotients to minimization when p divides a1, giving closed Frobenius formulas for almost arithmetic progression generators and partially solving a prior open problem.

  2. The Frobenius Formula for $A=(a,ha+d,ha+b_2d,...,ha+b_kd)$

    math.CO 2023-04 unverdicted novelty 4.0

    Extends the stable property of Frobenius numbers to sequences A(a)=(a, ha+dB) yielding a congruence-class characterization of g(A(a)) mod bk for large a, plus explicit formulas for several B.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  1. [1]

    Adamaszek, M

    A. Adamaszek, M. Adamaszek, Combinatorics of the change-making problem , European. J. Comb. 31 (2010), 47–63

    work page 2010

  2. [2]

    Brauer, On a problem of partitions , Amer

    A. Brauer, On a problem of partitions , Amer. J. Math. 64 (1942), 299–312

    work page 1942

  3. [3]

    Brauer, J

    A. Brauer, J. E. Shockley, On a problem of Frobenius, J. Reine Angew Math. 211 (1962), 215-220

    work page 1962

  4. [4]

    T. C. Brown, P. J. Shiue, A remark related to Froenius problem , Fibonacci Quart. 31 (1993), 31-36

    work page 1993

  5. [5]

    Denham, Short generating functions for some semigroup algebras , Electron

    G. Denham, Short generating functions for some semigroup algebras , Electron. J. Comb. 10 (2003), #R36

    work page 2003

  6. [6]

    A. L. Dulmage, N. S. Mendelsohn, Gaps in the exponent set of primitive matrices , Illinois J. Math. 8 (1964), 642-656

    work page 1964

  7. [7]

    Einstein, D

    D. Einstein, D. Lichtblau, A. Strzebonski, S. Wagon, Frobenius numbers by lattice point enumeration, Integers. 7 (2007), A15

    work page 2007

  8. [8]

    Greenberg, Solution to a linear diophantine equation for nonnegative integers , J

    H. Greenberg, Solution to a linear diophantine equation for nonnegative integers , J. Algo- rithms. 9(3) (1988), 343-535

    work page 1988

  9. [9]

    Hujter, On the lowest value of the Frobenius number , Technical Report MN/31 Com- puter and Automation Inst., Hungarian Academy of Sciences, (1987)

    M. Hujter, On the lowest value of the Frobenius number , Technical Report MN/31 Com- puter and Automation Inst., Hungarian Academy of Sciences, (1987)

    work page 1987

  10. [10]

    Kannan, Lattice translates of a polytope and the Frobenius problem , Combinatorica

    R. Kannan, Lattice translates of a polytope and the Frobenius problem , Combinatorica. 12(2) (1992), 161–177

    work page 1992

  11. [11]

    Komatsu, Sylvester power and weighted sums on the Frobenius set in arithmetic pro- gression, arXiv:2204.07325, 2022

    T. Komatsu, Sylvester power and weighted sums on the Frobenius set in arithmetic pro- gression, arXiv:2204.07325, 2022

    work page arXiv 2022

  12. [12]

    Komatsu, Y

    T. Komatsu, Y. Zhang, Weighted Sylvester sums on the Frobenius set , Irish Math. Soc. Bull. 87 (2021), 21-29

    work page 2021

  13. [13]

    Komatsu, Y

    T. Komatsu, Y. Zhang, Weighted Sylvester sums on the Frobenius set in more variables , Kyushu J. Math. 76 (2022), 163-175. FROBENIUS NUMBERS OF SPECIAL SEQUENCES 29

    work page 2022

  14. [14]

    Komatsu, Sylvester sum on the Frobenius set in arithmetic progression with initial gaps, arXiv:2210.17019v1, 2022

    T. Komatsu, Sylvester sum on the Frobenius set in arithmetic progression with initial gaps, arXiv:2210.17019v1, 2022

    work page arXiv 2022

  15. [15]

    K¨ oppe, S

    M. K¨ oppe, S. Verdoolaege, K. M. Woods, An implementation of the Barvinok–Woods integer projection algorithm, Information Theory and Statistical Learning. (2008)

    work page 2008

  16. [16]

    F. Liu, G. Xin, On Frobenius formulas of power sequences , arXiv:2210.02722, 2022

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  17. [17]

    J. A. De Loera, R. Hemmecke, J. Tauzer, R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), 1273-1302

    work page 2004

  18. [18]

    J. L. Ram´ ırez Alfons´ ın,Complexity of the Frobenius problem, Combinatorica. 16(1) (1996), 143–147

    work page 1996

  19. [19]

    J. L. Ram´ ırez Alfons´ ın,The Diophantine Frobenius Problem , Oxford Lecture Series in Mathematics and Its Applications, vol. 30, Oxford University Press, 2005

    work page 2005

  20. [20]

    J. B. Roberts, Note on linear forms , Proc. Amer. Math. Soc. 7 (1956), 465–469

    work page 1956

  21. [21]

    ¨O. J. R¨ odseth,On a linear diophantine problem of Frobenius II , J. Reine Angew Math. 307/308 (1979), 431–440

    work page 1979

  22. [22]

    J. J. Sylvester, On the partition of numbers, Quart.J. Pure Appl. Math. 1 (1857), 141-152

    work page

  23. [23]

    J. J. Sylvester, On sub-invariants, i.e., semi-invariants to binary quanties of an unlimited order, Amer. J. Math. 5 (1882), 119–136

    work page

  24. [24]

    E. S. Selmer, On the linear Diophantine problem of Frobenius , J. Reine Angew. Math. 293/294 (1977), 1–17

    work page 1977

  25. [25]

    R. P. Stanley, Enumerative combinatorics (volume 1) , Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, 2012

    work page 2012

  26. [26]

    Tripathi, On sums of positive integers that are not of the form ax +by, Amer

    A. Tripathi, On sums of positive integers that are not of the form ax +by, Amer. Math. Monthly. 115 (2008), 363–364

    work page 2008

  27. [27]

    Tripathi, The Frobenius problem for modified arithmetic progressions , J

    A. Tripathi, The Frobenius problem for modified arithmetic progressions , J. Integer Seq. 16(7) (2013), 13.7.4

    work page 2013

  28. [28]

    Tripathi, On the Frobenius problem for {a,ha +d,ha +bd,ha +b2d,...,ha +bkd}, J

    A. Tripathi, On the Frobenius problem for {a,ha +d,ha +bd,ha +b2d,...,ha +bkd}, J. Number Theory. 162 (2016), 212-223

    work page 2016

  29. [29]

    Tripathi, Formulate for the frobenius number in three variables, J

    A. Tripathi, Formulate for the frobenius number in three variables, J. Number Theory. 170 (2017), 368-389

    work page 2017

  30. [30]

    W. Wang, T. Wang, Alternate Sylvester sum on the Frobenius set , Comput. Nath. Appl. 56 (2008), 1328-1334

    work page 2008

  31. [31]

    Xin, A fast algorithm for MacMahon’s partition analysis , Electron

    G. Xin, A fast algorithm for MacMahon’s partition analysis , Electron. J. Combin. 11 (2004), R58 (electronic)

    work page 2004

  32. [32]

    Xin, A Euclid style algorithm for MacMahon’s partition analysis , J

    G. Xin, A Euclid style algorithm for MacMahon’s partition analysis , J. Combin Theory, Series A. 131 (2015), 32–60. Appendix A. the formula of f(x) Proposition A.1. Let A = (a,ha +d,ha +jd), a,j > 2, and a = kj−t,k ≥ 1, 0≤ t≤ j− 1,gcd (a,d ) = 1,d≤h. Suppsoe hk +d−ht≥ 0. Then f(x) = 1−xj(ha+d) 1−xha+d · (1−x(ha+jd)(k−1)) 1−xha+jd + x(k−1)(ha+jd)(1−x(ha+d)...

    work page 2015