(p.185) Appendix A Problems and conjectures
(p.185) Appendix A Problems and conjectures
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={\displaystyle \sum _{i\in s}}{a}_{i}?$
Vizvári conjecture^{1} 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,c≤n, (a,b,c)=1}.
Conjecture A.2.1. Is it true that sup_{n} $\left(\frac{1}{{X}_{n}}\right)$
Conjecture A.2.2. Does $\underset{n\to \infty}{\mathrm{lim}}}{\displaystyle \sum _{\left(a,b,c\right)\in {X}_{n}}}\frac{g\left(a,b,c\right)abc}{\sqrt{abc}$ 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 $\underset{\frac{ab}{c}\to \infty}{\mathrm{lim}\text{}\mathrm{inf}}}\frac{g\left(a,b,c\right)}{\sqrt{abc}}.$
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 krepresentable 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 krepresentable 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 _{2}−a _{1}−a _{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 ${\left(\frac{1}{2}n!\Pi A\right)}^{\frac{1}{n1}}\Sigma 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 m≥P _{3} (cf. Theorem 4.5.1 part b) and if P _{3}−S _{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 _{3}−S _{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})#P−complete?
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\left({a}_{1},\dots ,{a}_{n}\right)/\left(g\left({a}_{1},\dots ,{a}_{n}\right)1\right)\le 1\frac{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, pseudosymmetric 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
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 ≤ i ≤ N(S)when S = < s _{1}, s _{2} > ?
We know that l _{N(S)} = s _{1} s _{2}−s _{1}−s _{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 ith gap of a semigroup is as hard as to calculate the Frobenius number. Indeed, for calculating the ith 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 l_{i} for each 1 ≤ i ≤ N(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 n(ρ_{i}) denotes the number of gaps smaller than ρ_{i} where ρ_{i} denotes the ith nongap of S.
Problem A.5.4 Is n(ρ_{i}) computable in polynomial time?
A.6 Miscellaneous
The major unsolved analytic problem of Shellsort is to determine the asymptotic behaviour of its average running time. Discovering increment sequences for Shellsort 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 Shellsort 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},…,a_{n})(respectively N _{k}(m;a _{1},…, a _{n})) is the number of komitted natural nonnegative numbers and (respectively the largest of the komitted 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 ${\Omega}_{k}\left(m;{a}_{1},\dots ,{a}_{n}\right)>\frac{k\left(m;{a}_{1},\dots ,{a}_{n}\right)}{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 S ⊆ M 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 inequality ∣U∣ − ∣S∣ ≥ k:

(i) ∣S∣ ≤ m−k and

(ii) for any positive integers p and q such that $p<q<k,\frac{pm}{q}\notin 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 I_{S} 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̧stowskiWachtel, 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≤t≤n 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 nontrivial lower bound for f(n)?perhaps, $f\left(n\right)>{n}^{\frac{1}{3}\in}?$
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.14^{2} 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 _{j}−a _{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)