Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester
HTML articles powered by AMS MathViewer
- by R. J. Simpson and R. Tijdeman PDF
- Proc. Amer. Math. Soc. 131 (2003), 1661-1671 Request permission
Abstract:
Let ${\vec {v_0},..., \vec {v_k}}$ be vectors in $\mathbf {Z}^k$ which generate $\mathbf {Z}^k$. We show that a body $V \subset \mathbf {Z}^k$ with the vectors ${\vec {v_0},..., \vec {v_k}}$ as edge vectors is an almost minimal set with the property that every function $f: V \rightarrow \mathbf {R}$ with periods ${\vec {v_0},..., \vec {v_k}}$ is constant. For $k=1$ the result reduces to the theorem of Fine and Wilf, which is a refinement of the famous Periodicity Lemma. Suppose $\vec {0}$ is not a non-trivial linear combination of ${\vec {v_0},..., \vec {v_k}}$ with non-negative coefficients. Then we describe the sector such that every interior integer point of the sector is a linear combination of ${\vec {v_0},..., \vec {v_k}}$ over $\mathbf {Z}_{\geq 0}$, but infinitely many points on each of its hyperfaces are not. For $k=1$ the result reduces to a formula of Sylvester corresponding to Frobenius’ Coin-changing Problem in the case of coins of two denominations.References
- A. Amir, G.E. Benson, Alphabet independent two-dimensional pattern matching, Proc. 24th ACM Symp. Theory on Comp. (1992) pp. 59-68.
- M. Gabriella Castelli, Filippo Mignosi, and Antonio Restivo, Fine and Wilf’s theorem for three periods and a generalization of Sturmian words, Theoret. Comput. Sci. 218 (1999), no. 1, 83–94. WORDS (Rouen, 1997). MR 1687764, DOI 10.1016/S0304-3975(98)00251-5
- N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965), 109–114. MR 174934, DOI 10.1090/S0002-9939-1965-0174934-9
- R. Giancarlo and F. Mignosi, Generalizations of the periodicity theorem of Fine and Wilf, Trees in algebra and programming—CAAP ’94 (Edinburgh, 1994) Lecture Notes in Comput. Sci., vol. 787, Springer, Berlin, 1994, pp. 130–141. MR 1286756, DOI 10.1007/BFb0017478
- Z. Galil, K. Park, Truly alphabet independent two-dimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992), 247-256.
- Shunji Ito and Minako Kimura, On Rauzy fractal, Japan J. Indust. Appl. Math. 8 (1991), no. 3, 461–486. MR 1137652, DOI 10.1007/BF03167147
- Jacques Justin, On a paper by M. Castelli, F. Mignosi, A. Restivo. Comment on: “Fine and Wilf’s theorem for three periods and a generalization of Sturmian words” [Theoret. Comput. Sci. 218 (1999), no. 1, 83–94; MR1687764 (2000c:68110)], Theor. Inform. Appl. 34 (2000), no. 5, 373–377 (English, with English and French summaries). MR 1829233, DOI 10.1051/ita:2000122
- F. Mignosi, A. Restivo, P.V. Silva, On Fine and Wilf’s theorem for bidimensional words, to appear in Theor. Computer Sc.
- H. Ray, R.J. Simpson, The Frobenius problem in two dimensions, in preparation.
- Mireille Régnier and Ladan Rostami, A unifying look at $d$-dimensional periodicities and space coverings, Combinatorial pattern matching (Padova, 1993) Lecture Notes in Comput. Sci., vol. 684, Springer, Berlin, 1993, pp. 215–227. MR 1253337, DOI 10.1007/BFb0029807
- Öystein J. Rödseth, On a linear Diophantine problem of Frobenius, J. Reine Angew. Math. 301 (1978), 171–178. MR 557016, DOI 10.1515/crll.1978.301.171
- Ernst S. Selmer, On the linear Diophantine problem of Frobenius, J. Reine Angew. Math. 293(294) (1977), 1–17. MR 441855, DOI 10.1515/crll.1977.293-294.1
- Ernst S. Selmer and Öyvind Beyer, On the linear Diophantine problem of Frobenius in three variables, J. Reine Angew. Math. 301 (1978), 161–170. MR 557015
- C. Smoryński, Skolem’s solution to a problem of Frobenius, Math. Intelligencer 3 (1980/81), no. 3, 123–132. MR 642131, DOI 10.1007/BF03022866
- J.J. Sylvester, Mathematical questions, with their solutions, Educational Times 41 (1884), 21.
- R. Tijdeman and L. Zamboni, The Fine and Wilf theorem for any number of periods, in preparation.
Additional Information
- R. J. Simpson
- Affiliation: Department of Mathematics and Statistics, Curtin University of Technology, P.O. Box U1987, Perth, Western Australia 6001, Australia
- Email: simpson@maths.curtin.edu.au
- R. Tijdeman
- Affiliation: Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands
- MR Author ID: 172600
- Email: tijdeman@math.leidenuniv.nl
- Received by editor(s): December 31, 2001
- Published electronically: January 15, 2003
- Communicated by: David E. Rohrlich
- © Copyright 2003 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 131 (2003), 1661-1671
- MSC (2000): Primary 05D99, 06B25, 11Axx, 11B75, 68R15
- DOI: https://doi.org/10.1090/S0002-9939-03-06970-3
- MathSciNet review: 1953570