A Diophantine transport problem from 2016 and its possible solution from 1903
Keywords:
Linear Diophantine inequalities, solutions in nonnegative integers, transport problem, generating functions, Laurent series, nice rational functionsAbstract
Motivated by a recent Diophantine transport problem about how to transport prof- itably a group of persons or objects, we survey classical facts about solving systems of linear Diophantine equations and inequalities in nonnegative integers. We emphasize on the method of Elliott from 1903 and its further development by MacMahon in his “Ω-Calculus” or Partition Analysis. As an illustration we obtain the solution of the considered transport problem in terms of a formal power series in several variables which is an expansion of a rational function of a special form.
References
H. Abdulrab, M. Maksimenko. General solution of linear Diophantine equations and in- equations. In: “Rewriting techniques and applications. 6th International Conference, RTA- 95, Kaiserslautern, Germany, April 5–7, 1995”, Lecture Notes in Computer Science, vol. 914, Springer-Verlag, Berlin, 1995, 339–351.
W. Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann., 99 (1928), 118–133.
F. Ajili, E. Contejean. Complete solving of linear Diophantine equations and inequations without adding variables. In: “Principles and Practice of Constraint Programming – CP’95 (Cassis, 1995), Lecture Notes in Comput. Sci., vol. 976, Springer-Verlag, Berlin, 1995, 1–17.
G. E. Andrews. MacMahon’s partition analysis. I: The lecture Hall partition theorem. In: Mathematical Essays in Honor of Gian-Carlo Rota’s 65th Birthday (eds B. E. Sagan et al.) Prog. Math., vol. 161, Birkh¨auser, Boston, MA, 1998, 1–22.
G. E. Andrews, P. Paule. MacMahon’s partition analysis. XII: Plane partitions. J. Lond. Math. Soc., II. Ser., 76 (2007), No. 3, 647–666.
G. E. Andrews, P. Paule, A. Riese. MacMahon’s partition analysis: The Omega pack- age. Eur. J. Comb., 22, 7 (2001), 887–904.
G. E. Andrews, P. Paule, A. Riese. MacMahon’s partition analysis. VI: A new reduction algorithm. Ann. Comb., 5 (2001), 251–270.
M. Aschenbrenner, W. Y. Pong. Orderings of monomial ideals. Fundam. Math., 181 (2004), No. 1, 27–74.
L. Bedratyuk, G. Xin. MacMahon partition analysis and the Poincar´e series of the algebras of invariants of ternary and quaternary forms. Linear Multilinear Algebra, 59 (2011), 789–799.
A. Berele. Applications of Belov’s theorem to the cocharacter sequence of p.i. algebras. J. Algebra, 298 (2006), 208–214.
A. Berele. Properties of hook Schur functions with applications to p. i. algebras. Adv. Appl. Math., 41 (2008), 52–75.
F. Benanti, S.Boumova, V. Drensky, G. Genov, P. Koev. Computing with rational symmetric functions and applications to invariant theory and PI-algebras, Serdica Math. J., 38 (2012), No. 1–3, 137–188.
G. R. Blakley. Combinatorial remarks on partitions of a multipartite number. Duke Math. J., 31 (1964), 335–340; Errata Ibid. 31 (1964), 718.
Y. A. Bogoyavlenskiy, D. G. Korzun. A software system for remote solving homogenous linear diophantine equations in non-negative integers. St. Petersburg State Polytechnical University J., Computer Science, Telecommunication and Control Systems, (2010), No. 1(93), 90–99 (in Russian).
E. Contejean. Solving linear Diophantine constraints incrementally, in “Logic program- ming (Budapest, 1993)”. MIT Press Ser. Logic Program., Cambridge, MA, MIT Press, 1993, 532–549.
L. E. Dickson. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. Math., 35 (1913), No. 4, 413–422.
E. Domenjoud, A. P. Toma´s. From Elliott-MacMahon to an algorithm for general linear constraints on naturals. In: “Principles and Practice of Constraint Programming – CP’95 (Cassis, 1995), Lecture Notes in Comput. Sci., vol. 976, Berlin, Springer-Verlag, 1995, 18–35.
V. Drensky, C. K. Gupta. Constants of Weitzenb¨ock derivations and invariants of unipo- tent transformations acting on relatively free algebras. J. Algebra, 292 (2005), 393–428.
E. B. Elliott. On linear homogeneous diophantine equations. Quart. J. Pure Appl. Math., 34 (1903), 348–377.
L. Euler. Introductio in Analysin Infinitorum, Vol. I, Bousquet, Lausanne, M.-M. 1748. Reprinted as: Leonhardi Euleri Opera Omnia, Ser. I, Vol. VIII (eds A. Krazer, F. Rudio). Teubner, Leipzig, 1922; German translation by H. Maser: Einleitung in die Analysis des Unendlichen, Erster Teil, Springer-Verlag, Berlin, 1885, reprinted: 1983.
