An application of gomory cuts in number theory

Frobenius has stated the following problem. Suppose thata ₁, a₂, ?, a_n are given positive integers and g.c.d. (a ₁, ? , a_n) = 1. The problem is to determine the greatest positive integerg so that the equation $$\sum\limits_{i = 1}^n {a_i x_i = g} $$ has no nonnegative integer solution. Showing the interrelation of the original problem and discrete optimization we give lower bounds for this number using Gomory cuts which are tools for solving discrete programming problems. In the first section an important theorem is cited after some remarks. In Section 2 we state a parametric knapsack problem. The Frobenius problem is equivalent with finding the value of the parameter where the optimal objective function value is maximal. The basis of this reformulation is the above mentioned theorem. Gomory's cutting plane method is applied for the knapsack problem in Section 3. Only one cut is generated and we make one dual simplex step after cutting the linear programming optimum of the knapsack problem. Applying this result we gain lower bounds for the Frobenius problem in Section 4. In the last section we show that the bounds are sharp in the sense that there are examples with arbitrary many coefficients where the lower bounds and the exact solution of the Frobenius problem coincide.     

Complexity of the Frobenius problem

Consider the Frobenius Problem: Given positive integersa ₁,...,a _n witha _i 2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa ₁,...,a _n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions.     

The asymptotic distribution of Frobenius numbers

The Frobenius number F(a) of an integer vector a with positive coprime coefficients is defined as the largest number that does not have a representation as a positive integer linear combination of the coefficients of a. We show that if a is taken to be random in an expanding d-dimensional domain, then F(a) has a limit distribution, which is given by the probability distribution for the covering radius of a certain simplex with respect to a (d−1)-dimensional random lattice. This result extends recent studies for d=3 by Arnold, Bourgain-Sinai and Shur-Sinai-Ustinov. The key features of our approach are (a) a novel interpretation of the Frobenius number in terms of the dynamics of a certain group action on the space of d-dimensional lattices, and (b) an equidistribution theorem for a multidimensional Farey sequence on closed horospheres.     

Frobenius Problem and dead ends in integers

Let a and b be positive and relatively prime integers. We show that the following are equivalent: (i) d is a dead end in the (symmetric) Cayley graph of Z with respect to a and b, (ii) d is a Frobenius value with respect to a and b (it cannot be written as a non-negative or non-positive integer linear combination of a and b), and d is maximal (in the Cayley graph) with respect to this property. In addition, for given integers a and b, we explicitly describe all such elements in Z. Finally, we show that Z has only finitely many dead ends with respect to any finite symmetric generating set. In Appendix A we show that every finitely generated group has a generating set with respect to which dead ends exist.     

An application of an optimal behaviour of the greedy solution in number theory

Leta ₁,a ₂, ...,a _n be relative prime positive integers. The Frobenius problem is to determine the greatest integer not belonging to the set { _j=1 ⁿ a _j x _j :xZ ₊ ⁿ }. The Frobenius problem belongs to the combinatorial number theory, which is very rich in methods. In this paper the Frobenius problem is handled by integer programming which is a new tool in this field. Some new upper bounds and exact solutions of subproblems are provided. A lot of earlier results obtained with very different methods can be discussed in a unified way.     

Atoms of the set of numerical semigroups with fixed Frobenius number

Given a positive integer g, we denote by F(g) the set of all numerical semigroups with Frobenius number g. The set (F(g),∩) is a semigroup. In this paper we study the generators of this semigroup.     

The Frobenius Complex

Motivated by the classical Frobenius problem, we introduce the Frobenius poset on the integers ${\mathbb Z}$ , that is, for a sub-semigroup ?? of the non-negative integers ( ${\mathbb N}$ , +), we define the order by n ??_?? m if ${{m-n \in \Lambda}}$ . When ?? is generated by two relatively prime integers a and b, we show that the order complex of an interval in the Frobenius poset is either contractible or homotopy equivalent to a sphere. We also show that when ?? is generated by the integers {a, a?+?d, a?+?2d, . . . , a?+?(a?1)d}, the order complex is homotopy equivalent to a wedge of spheres.     

On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

Solution to a linear diophantine equation for nonnegative integers

We solve the 3-variable problem: find integers x ≥ 0, y ≥ 0, z ≥ 0 that satisfy ax + by + cz = L for given integers a, b, c, L, where 1 < a < b < c < L. The method of solution is related to the one for the Frobenius problem in three variables, which has been solved by Selmer and Beyer and by Rödseth (J. Reine Angew. Math.301 (1978), 161–178). These methods take O(a) steps, in the worst case, to find the Frobenius value. The method here, for the Frobenius value, is shown to be rapid, requiring less than O(log a) steps. The diophantine equation is then solved with little extra effort to result in an O(log a) method overall.     

Periodic decomposition of measurable integer valued functions

We study those functions that can be written as a sum of (almost everywhere) integer valued periodic measurable functions with given periods. We show that being (almost everywhere) integer valued measurable function and having a real valued periodic decomposition with the given periods is not enough. We characterize those periods for which this condition is enough. We also get that the class of bounded measurable (almost everywhere) integer valued functions does not have the so-called decomposition property. We characterize those periods a₁,…,ak for which an almost everywhere integer valued bounded measurable function f has an almost everywhere integer valued bounded measurable (a₁,…,ak)-periodic decomposition if and only if Δa₁?Δakf=0, where Δaf(x)=f(x+a)−f(x).     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

Modular retractions of numerical semigroups

Let S be a numerical semigroup, let m be a nonzero element of S, and let a be a nonnegative integer. We denote ${\rm R}(S,a,m) = \{ s-as \bmod m \mid s \in S \}$ (where asmodm is the remainder of the division of as by m). In this paper we characterize the pairs (a,m) such that ${\rm R}(S,a,m)$ is a numerical semigroup. In this way, if we have a pair (a,m) with such characteristics, then we can reduce the problem of computing the genus of S=〈n ₁,…,n _p 〉 to computing the genus of a “smaller” numerical semigroup 〈n ₁?an ₁modm,…,n _p ?an _p modm〉. This reduction is also useful for estimating other important invariants of S such as the Frobenius number and the type.     

A Hardy field extension of Szemerédi's theorem

In 1975 Szemerédi proved that a set of integers of positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman showed in 1996 that the common difference of the arithmetic progression can be a square, a cube, or more generally of the form p(n) where p(n) is any integer polynomial with zero constant term. We produce a variety of new results of this type related to sequences that are not polynomial. We show that the common difference of the progression in Szemerédi's theorem can be of the form [nδ] where δ is any positive real number and [x] denotes the integer part of x. More generally, the common difference can be of the form [a(n)] where a(x) is any function that is a member of a Hardy field and satisfies a(x)/xk→∞ and a(x)/xk+1→0 for some non-negative integer k. The proof combines a new structural result for Hardy sequences, techniques from ergodic theory, and some recent equidistribution results of sequences on nilmanifolds.     

Bounds for the greatest characteristic root of an irreducible nonnegative matrix

A new lower bound for the Perron root for irreducible, non-negative matrices is obtained which is, in particular, a better bound than the Frobenius bound [w = max(a_kk)] if all the main diagonal elements are zero.     

Geometry of continued fractions associated with Frobenius numbers

The article describes the interrelations between the minimal integer number N(a,b,c) which belongs to the additive semigroup of integers generated by a, b, c together with all greater integers, on the one hand, and the geometrical theory of continued fractions describing the convex hulls of sets of integer points in simplicial cones, on the other hand. It also provides some hints on the extension of N to non-integral arguments.     

An optimal lower bound for the Frobenius problem

Given N?2 positive integers a₁,a₂,…,aN with GCD(a₁,…,aN)=1, let fN denote the largest natural number which is not a positive integer combination of a₁,…,aN. This paper gives an optimal lower bound for fN in terms of the absolute inhomogeneous minimum of the standard (N−1)-simplex.     

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax−by⩽z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions.Nonmonotone integer programs are optimization problems with constraints of the type ax+by⩽z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe.The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover.Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.     

Number of lattice points in a sphere

A new estimate is obtained for the residue R in the asymptotics of the number of integer points in a ball of radius a. The estimate has the form R ? a ^{17/14 + ?} .     

Repdigit Keith numbers

A Keith number is a positive integer N with the decimal representation a ₁ a ₂?a _k such that k ≥ 2 and N appears in the sequence that starts with a ₁, a ₂,…, a _k and for which each term afterwards is the sum of the k preceding terms. In 2007, Klazar and Luca [M. Klazar and F. Luca, Counting Keith numbers, J. Integer Seq., 10(2):Article 07.2.2, 2007] proved that there are only finitely many Keith numbers with only one distinct digit (so-called repdigits). In this paper, we prove that there are no Keith numbers which are repdigits.