Geometric proof of R\o dseth's formula for Frobenius numbers

A. V. Ustinov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Number theory, algebra, and analysis, Tome 276 (2012), pp. 280-287.

Résumé

Using a geometric interpretation of continued fractions, we give a new proof of Rødseth's formula for Frobenius numbers.

Bibliographie

[1] Arnold V.I., Eksperimentalnoe nablyudenie matematicheskikh faktov, MTsNMO, M., 2006 | MR

[2] Burgein Zh., Sinai Ya.G., “Predelnoe povedenie bolshikh chisel Frobeniusa”, UMN, 62:4 (2007), 77–90 | DOI | MR

[3] Vorobev I.S., “Eksperimentalnoe issledovanie problemy Frobeniusa dlya trekh argumentov”, Dalnevost. mat. zhurn., 11:1 (2011), 3–9 | MR | Zbl

[4] Kan I.D., “K probleme Frobeniusa”, Fund. i prikl. matematika, 3:3 (1997), 821–835 | MR | Zbl

[5] Kan I.D., “Problema Frobeniusa dlya klassov polinomialnoi razreshimosti”, Mat. zametki, 70:6 (2001), 845–853 | DOI | MR | Zbl

[6] Ustinov A.V., Prilozheniya summ Klostermana v arifmetike i geometrii, Lambert Acad. Publ., Saarbrücken, 2011

[7] Ustinov A.V., “Reshenie zadachi Arnolda o slaboi asimptotike dlya chisel Frobeniusa s tremya argumentami”, Mat. sb., 200:4 (2009), 131–160 | DOI | MR | Zbl

[8] Ustinov A.V., “O raspredelenii chisel Frobeniusa s tremya argumentami”, Izv. RAN. Ser. mat., 74:5 (2010), 145–170 | DOI | MR | Zbl

[9] Frolenkov D.A., “Srednee znachenie chisel Frobeniusa s tremya argumentami”, Izv. RAN. Ser. mat. (to appear)

[10] Aicardi F., “On the geometry of the Frobenius problem”, Funct. Anal. Other Math., 2 (2009), 111–127 | DOI | MR | Zbl

[11] Aliev I., Henk M., “Integer knapsacks: average behavior of the Frobenius numbers”, Math. Oper. Res., 34:3 (2009), 698–705 | DOI | MR | Zbl

[12] Aliev I., Henk M., Hinrichs A., “Expected Frobenius numbers”, J. Comb. Theory A., 118:2 (2011), 525–531 | DOI | MR | Zbl

[13] Arnold V.I., Arnold's problems, Springer, Berlin, 2004 | MR

[14] Arnold V.I., “Geometry of continued fractions associated with Frobenius numbers”, Funct. Anal. Other Math., 2 (2009), 129–138 | DOI | MR | Zbl

[15] Bermond J.-C., Comellas F., Hsu D.F., “Distributed loop computer networks: A survey”, J. Parallel Distrib. Comput., 24 (1995), 2–10 | DOI

[16] Brauer A., Shockley J.E., “On a problem of Frobenius”, J. reine angew. Math., 211 (1962), 215–220 | MR | Zbl

[17] Davison J.L., “On the linear Diophantine problem of Frobenius”, J. Number Theory., 48 (1994), 353–363 | DOI | MR | Zbl

[18] Denham G., “Short generating functions for some semigroup algebras”, Electron. J. Comb., 10 (2003), Pap. R36 | MR

[19] Einstein D., Lichtblau D., Strzebonski A., Wagon S., “Frobenius numbers by lattice point enumeration”, Integers, 7:1 (2007), Pap. A15 | MR

[20] Fel L.G., “Frobenius problem for semigroups $\mathsf S(d_1,d_2,d_3)$”, Funct. Anal. Other Math., 1 (2006), 119–157 | DOI | MR | Zbl

[21] Fel L.G., “Analytic representations in the three-dimensional Frobenius problem”, Funct. Anal. Other Math., 2 (2008), 27–44 | DOI | MR | Zbl

[22] Hofmeister G.R., “Zu einem Problem von Frobenius”, Norske Vid. Selsk. Skr., 1966, no. 5, 1–37 | MR

[23] Hwang F.K., “A survey on double loop networks”, Reliability of computer and communication networks, New Brunswick, NJ, 1989, DIMACS Ser. Discrete Math. Theor. Comput. Sci., 5, Amer. Math. Soc., Providence, RI, 1991, 143–151 | MR

[24] Hwang F.K., “A complementary survey on double-loop networks”, Theor. Comput. Sci., 263 (2001), 211–229 | DOI | MR | Zbl

[25] Johnson S.M., “A linear diophantine problem”, Can. J. Math., 12 (1960), 390–398 | DOI | MR | Zbl

[26] Kannan R., “Lattice translates of a polytope and the Frobenius problem”, Combinatorica, 12:2 (1992), 161–177 | DOI | MR | Zbl

[27] Karp R.M., “Reducibility among combinatorial problems”, Complexity of computer computations, Ed. by R.E. Miller, J.W. Thatcher, Plenum Press, New York, 1972, 85–103 | DOI | MR

[28] Marklof J., “The asymptotic distribution of Frobenius numbers”, Invent. math., 181 (2010), 179–207 | DOI | MR | Zbl

[29] Marklof J., Strömbergsson A., Diameters of random circulant graphs, E-print, 2011, arXiv: 1103.3152v2 [math.CO] | MR

[30] Nijenhuis M., “A minimal-path algorithm for the “money changing problem””, Amer. Math. Mon., 86 (1979), 832–835 ; Correction, Amer. Math. Mon., 87 (1980), 377 | DOI | MR | Zbl | DOI | MR

[31] Ramírez Alfonsín J.L., The Diophantine Frobenius problem, Oxford Univ. Press, Oxford, 2005 | MR | Zbl

[32] Rödseth Ö.J., “On a linear Diophantine problem of Frobenius”, J. reine angew. Math., 301 (1978), 171–178 | MR | Zbl

[33] Rödseth Ö.J., “Weighted multi-connected loop networks”, Discrete Math., 148 (1996), 161–173 | DOI | MR | Zbl

[34] Selmer E.S., “On the linear Diophantine problem of Frobenius”, J. reine angew. Math., 293–294 (1977), 1–17 | MR | Zbl

[35] Selmer E.S., Beyer Ö., “On the linear diophantine problem of Frobenius in three variables”, J. reine angew. Math., 301 (1978), 161–170 | MR | Zbl

[36] Shchur V., Sinai Ya., Ustinov A., “Limiting distribution of Frobenius numbers for $n=3$”, J. Number Theory., 129:11 (2009), 2778–2789 | DOI | MR | Zbl

[37] Sylvester J.J., “Question 7382”, Educ. Times, 37 (1884), 26

[38] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21 (1974), 392–402 | DOI | MR | Zbl