Jump to ContentJump to Main Navigation
The Diophantine Frobenius Problem$

Jorge L. Ramírez Alfonsín

Print publication date: 2005

Print ISBN-13: 9780198568209

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198568209.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 25 February 2017

(p.185) Appendix A Problems and conjectures

(p.185) Appendix A Problems and conjectures

The Diophantine Frobenius Problem
Oxford University Press

A.1 Algorithmic questions

It is known [342] that FP is 풩풫-hard under Turing reductions.

Problem A.1.1 Is FP 풩풫-complete (under Karp reductions)?

One may wonder whether the knowledge of the Frobenius number could help to find a desired representation. Consider the following promising question.

Problem A.1.2 Let a 1,…,a n and t be positive integers such that t>g(a 1,…,a n). Is there a polynomial time algorithm that finds s⊆{1,…,n} such that t = i s a i ?

Vizvári conjecture1 that there exists an integer K such that the above question is easy if t>K.

To show that FP is solvable in polynomial time with n fixed, Kannan [228] gave a polynomial time algorithm that finds the covering radius μ(P, L) for any convex set P in R n and any lattice L of dimension n also in R n with fixed n.

Problem A.1.3. Does there exist a polynomial time algorithm that finds μ(P,L) where P and L are defined as in Theorem 1.2.14?

Maybe the constructive version for the covering radius given in Corollary 1.2.16 could leads to such an algorithm. The following conjecture is due to L. Lovász.

Conjecture A.1.4. [280] If n is fixed and A is an integral matrix then the set of vectors b yielding maximal lattice free bodies (see Section (p.186) 1.2.1 for definitions) is the union of the set of lattice points contained in a polynomial number of polyhedra (with a particular lattice for each polyhedron).

Maximizing a linear function over the lattice points in each such polyhedron is a standard integer program which can be solved in polynomial time for a fixed number of variables (by using Lenstra’s algorithm [264]). So, if the Lovász conjecture were correct, this would yield to an alternative polynomial algorithm for FP.

A.2 g(a 1,…,a n)

Davison has proposed the following two conjectures [104, Conjectures 1 and 2]. Let a,b,c be positive integers and let X n= {(a,b,c)∣1≤a,b,cn, (a,b,c)=1}.

Conjecture A.2.1. Is it true that supn ( 1 X n )

( a , b , c ) X n ( g ( a , b , c ) a b c a b c ) < ?

Conjecture A.2.2. Does lim n ( a , b , c ) X n g ( a , b , c ) a b c a b c exist and is finite?

In [208], Hujter posed the following problem (cf. Theorem 3.6.2).

Problem A.2.3 Compute the exact value for lim inf a b c g ( a , b , c ) a b c .

After the general expresion for g(a 1, a 2, a 3) given in Theorem 2.2.3, an appealing question is to find a similar formula for n≥4.

Problem A.2.4 Is there an explicit formula for g(a 1, a 2, a 3, a 4)?

As Hujter remarks, Boros’ technique, via subadditive functions (cf. Theorem 3.1.20), seems to be very useful in order to obtain new results concerning FP.

Problem A.2.5 Develope the subadditive approach in relation to FP.

In [32], Beck and Robins generalized FP as follows. An integer m is said k-representable if d(m; a 1,…, a n)=k, that is, m can be represented in exactly k ways; see [343, 341, 450] for a closely related problem. Let g k(a 1,…,a n) be the largest no k-representable integer (it is easy to see that for each k, eventually all integers are representable at least k times). Thus, g 0(a 1,…,a n)= g(a 1…,a n). Beck and Robins found that g k(a 1, a 2)=(k+ 1)a 1 a 2a 1a 2. Their proof for the (p.187) latter is by induction and based in the fact that d(m+a 1 a 2;a 1, a 2)=d(m;a 1,a 2)+1. They proposed the following problem.

Problem A.2.6 Investigate gk(a 1,…,a n) when n≥3.

Supported by many computations, Beihoffer et al. [37] presented the following conjecture

Conjecture A.2.7. Let A={a 1,…,a n}. Then the expected value of g(A) is a small constant multiple of ( 1 2 n ! Π A ) 1 n 1 Σ A .

In [19, Problem 2003–5], Arnold has also posed a closely related question. In [17], Arnold proposed to investigate the asymptotical behaviour of what it was called the derivate

Problem A.2.8 What is the behaviour ofΔ(m;a 1,a 2,a 3)=d(m+1;a 1,a 2,a 3)−d(m;a 1,a 2,a 3)?

A.3 Denumerant

Problem A.3.1 Is computing d(m; a 1,…,a n) #풫−complete?

Note that d(m;a 1,a 2,a 3) is known if mP 3 (cf. Theorem 4.5.1 part b) and if P 3S 3+1 ≤ m<P 3 (cf. Corollary 4.5.3). In [408], Sertöz and Özlük proposd the following problem.

Problem A.3.2 Find a formula for d(m; a 1, a 2, a 3) when m<P 3S 3+1.

The following question turned up in [341] while investigating FP.

Problem A.3.3 Let p and q be prime numbers. Is there a polynomial time algorithm that finds d(m;p, p 2,…,p n, q, q 2,…,q n)?

This does not seem to be immediate even if we insist that p=3 and q=5.

A.4 N(a 1,…,a n)

Problem A.4.1 Is computing N(a 1,…,a n) 풩풫−complete?

Or perhaps,

Problem A.4.2 Is computing N(a 1,…,a n)#Pcomplete?

Selmer [392] has shown that the number N(a 1,…,a n) can be increased by the removal of some a i s.

(p.188) Problem A.4.3 Given integers a 1,…,a n, what is the influence of a new (independent) element a n+1 in N(a 1,…,a n)?

Wilf [480] proposed the following two problems.

Problem A.4.4 Is it true that for fixed n the fraction N ( a 1 , , a n ) / ( g ( a 1 , , a n ) - 1 ) 1 1 n with equality only for (a 1,…,a n)=(n, n+1,…,2n−1)?

Frőberg et al. [149] remarked that Lemmas 7.2.4 and 7.2.6 show that there is always equality in Wilf’s question if n=2. They also showed that Wilf’s question can be answered positively in the case n=3 by proving that the type of any semigroup S=< s 1,s 2,s 3> is at most two. Finally, they also showed that there is always equality for all semigroups S=< k, mk+1, mk+2, …,(m+1)k−1> since g(S)=mk−1, N(S)=m and the number of generators is k. In [121] Dobbs and Matthews answered Problem A.4.4 when the semigroup < a 1,…,a n> is symmetric, pseudo-symmetric or of maximal embedding dimension.

Problem A.4.5 Let q(n) be the number of semigroups having the same Frobenius number. What is the order of magnitude of q(n) for n → ∞ ?

In relation to ProblemA.4.5, Backelin [21] posed the following question.

Problem A.4.6 Find explicit formulas or good upper bounds for the quantities

K ( n , k , q ) = | { X { 1 , , n } : | X | = k , | 2 X | q } | .

Backelin [21] remarked that for q<3k−3 fairly good results for Problem A.4.6 can be obtained by means of [145, Theorem 1.9] and that [145, Theorem 2.8]may also yield good results in general.

A.5 Gaps

Recall that l 1,<···<l N(S) denotes the gaps (ordered increasingly) of the semigroup S where N(S)=# (N\S) is the genus of S; see Section 7.1.

Problem A.5.1 Let S=< s 1,…,s n>. Investigate the behaviour of the l i s.

In particular,

(p.189) Problem A.5.2 Is there an explicit formula that computes l i for each 1 ≤ iN(S)when S = < s 1, s 2 > ?

We know that l N(S) = s 1 s 2s 1s 2 but, for general n, the search for such a formula seems to be a difficult task. This is not very surprising since computing the i-th gap of a semigroup is as hard as to calculate the Frobenius number. Indeed, for calculating the i-th gap of a semigroup S we may calculate g N(S)−i(S)=g(S∪{g N(S)(S)}∪…∪{g N(S)−i+1(S)}) where g N(S)(S)=g(S).

May be a formula for gaps in some special sequences could be accesible.

Problem A.5.3 Let S= < a,a+d,… ,a+sd > with s ≥ 1 and (a,d)=1. Is there a formula that computes li for each 1 ≤ iN(S)?

This problem is solved [345] in the simplest case when s = 1. Notice that Theorem 3.3.2 gives a positive answer when i = N(S) for any integers a, s and d.

Recall that ni) denotes the number of gaps smaller than ρi where ρi denotes the i-th non-gap of S.

Problem A.5.4 Is ni) computable in polynomial time?

A.6 Miscellaneous

The major unsolved analytic problem of Shell-sort is to determine the asymptotic behaviour of its average running time. Discovering increment sequences for Shell-sort with better perfomance than those previously known is always a valuable practical result because the new sequence can be immediately used with only a one line change in the Shell-sort routine.

Problem A.6.1 Investigate further increment sequences for the Shellsort method.

Let I(a 1,…, a n) be the greatest number of elements that can be omitted without altering g(a 1,…, a n); see Section 3.5.

Problem A.6.2 What is the behaviour of I(a 1,…, a n)?

Recall that Ωk(m;a 1,…,an)(respectively N k(m;a 1,…, a n)) is the number of k-omitted natural non-negative numbers and (respectively the largest of the k-omitted numbers); see Section 6.2.

(p.190) Problem A.6.3 Study the functions Ωk(m;a 1, …, a n) and N k(m; a 1,…, a n) in the case n ≥ 3.

Skupień has posed the following problem.

Problem A.6.4 Characterize the sequences a 1,…, a n and the integers m such that Ω k ( m ; a 1 , , a n ) > k ( m ; a 1 , , a n ) 2 for all k∈{0,…, m−1}.

While investigated FP, Norman [314] came up with the following conjecture.

Conjecture A.6.5. Let M={0, 1,…, m−1}, let SM with 0∈S and let B= {b 1,…, b k} ⊂ M with b i ≠ 0 for all i and (m, d)=1 where (b 1,…, b k)=d. Let U =S+B (addition modulo m). Then, the following two conditions are sufficient for the inequalityU∣ − ∣S∣ ≥ k:

  • (i) ∣S∣ ≤ mk and

  • (ii) for any positive integers p and q such that p < q < k , p m q B .

    Furthermore, if the second condition is satisfied and the first is not then U =M.

Recall that N(t 1,…, t k, q) is the least integer such that if n > N(t 1,…,t k, q) and (t 1,…, t k) divides n then the vector space V n(q) admits a partition of type {t 1,…, t k}. In [190], Heden conjecture the following bound for N(t 1,…, t k, q).

Conjecture A.6.6. N(t 1,…, t k, q) < 2t k.

The following question turned up in [341] while investigating Problem A.3.3.

Problem A.6.7 Investigate the complexity of the following question. Given integer z, are there integers x and y such that x 2+ y 2=z?

Let I S be the toric ideal of the semigroup S and let α(I) denote the minimal number of generators of ideal I. Bresinsky [61, page 218] raised the following problem.

Problem A.6.8 Let S be a symmetric numerical semigroup. Does there exist an upper bound for α(I S) which depends only on the minimal number of generators of S?

If n=2 then α(I S)=1 because IS is a principal ideal in k[X 1, X 2].If n=3 Herzog [191] proved that α(I,S) =2. If n=4, Bresinsky (p.191) [61] proved that α(I S)≤5. If n=5, Bresinsky [63] proved that α(I S)≤13 under certain conditions; see [81] and [76, Section 5.1] for further details.

Guy [176] has posed several problems concerning the Sylver Coinage game. Notice that an answer to Problem A.4.3 may yield to a winning strategy for the Sylver Coinage game; see Section 5.6.1.

Problem A.6.9 Investigate further winning strategies for the Sylver coinage game.

Problem A.6.10 Generalize the results of the jugs problem when there are four or more jugs.

A.6.1 Erdős’ problems

In a rich and fruitful mailing (in relation to FP) with Chrza̧stowski-Wachtel, Erdős posed the following questions.

Problem A.6.11 What is the smallest integer f(n) for which one can divide the integers 1≤tn into f(n) classes so that n should not be the sum of a subset of the elements of the same class (i.e. n ≠ Σ x i u i with x i=0 or 1 and {u i} are in the same class) ?

Problem A.6.12 Is there a non-trivial lower bound for f(n)?perhaps, f ( n ) > n 1 3 ?

Problem A.6.13 Is it true that for every integer k there is a integer h(k) so that every prime p > h(k) if a 1,…,a k all less that p are any set of k integers one can always divide them into two classes so that p is not the sum of a subset of the numbers of the same class?

Problem A.6.142 Let a 1 < a 2 < ··· < a n+1 ≤ 2n be n+1 integers less than or equal to 2n. Trivially, two of them are consecutive and thus relatively prime. Is it true that there are (a i, a j)=1 where the smallest is less or equals to n? Also, is (a i, a j)=1 with a ja i > n−σ(n) solvable? i.e. are there two of them which are far apart and are realtively prime? If n−σ(n)|n is not true a weaker inequality might also be of interest. (p.192)


(1) Personal communication.

(2) In one of the letters’ Erdös wrote

‘this is a very annoying elementary problem of mine which I cannot solve’.