Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester


Authors: R. J. Simpson and R. Tijdeman
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
Published electronically: January 15, 2003
MathSciNet review: 1953570
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. A. Amir, G.E. Benson, Alphabet independent two-dimensional pattern matching, Proc. 24th ACM Symp. Theory on Comp. (1992) pp. 59-68.
  • 2. M.G. Castelli, F. Mignosi, A. Restivo, Fine and Wilf's theorem for three periods and a generalization of Sturmian words, Theor. Comput. Sci. 218 (1999), 83-94. MR 2000c:68110
  • 3. N.J. Fine, H.S. Wilf, Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc. 16 (1965), 109-114. MR 30:5124
  • 4. R. Giancarlo, F. Mignosi, Generalizations of the periodicity theorem of Fine and Wilf, CAAP '94, LNCS 787 (1994), 130-141. MR 95g:68091
  • 5. Z. Galil, K. Park, Truly alphabet independent two-dimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992), 247-256.
  • 6. Sh. Ito, M. Kimura, On Rauzy fractal, Japan J. Indust. Appl. Math. 8 (1991), 461-486. MR 93d:11084
  • 7. J. Justin, On a paper by Castelli, Mignosi, Restivo, RAIRO: Theoret. Informatics Appl. 34 (2000), 373-377. MR 2002d:68089
  • 8. F. Mignosi, A. Restivo, P.V. Silva, On Fine and Wilf's theorem for bidimensional words, to appear in Theor. Computer Sc.
  • 9. H. Ray, R.J. Simpson, The Frobenius problem in two dimensions, in preparation.
  • 10. M. Regnier, L. Rostami, A unifying look at $d$-dimensional periodicities and space coverings, Proc. 4th Symp. on Combinatorial Pattern Matching LNCS 684 (1993), 215-227. MR 94j:68310
  • 11. Ö. Rödseth, On a linear diophantine problem of Frobenius, J. reine angew. Math. 301 (1978), 171-178. MR 58:27741
  • 12. E.S. Selmer, On the linear diophantine problem of Frobenius, J. reine angew. Math. 293/294 (1977), 1-17. MR 56:246
  • 13. E.S. Selmer, Ö. Beyer, On the linear diophantine problem of Frobenius in three variables, J. reine angew. Math. 301 (1978), 161-170. MR 58:27740
  • 14. C. Smorynski, Skolem's solution to a problem of Frobenius, Math. Intelligencer 3 (1981), 123-132. MR 83b:03031
  • 15. J.J. Sylvester, Mathematical questions, with their solutions, Educational Times 41 (1884), 21.
  • 16. R. Tijdeman and L. Zamboni, The Fine and Wilf theorem for any number of periods, in preparation.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05D99, 06B25, 11Axx, 11B75, 68R15

Retrieve articles in all journals with MSC (2000): 05D99, 06B25, 11Axx, 11B75, 68R15


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
Email: tijdeman@math.leidenuniv.nl

DOI: https://doi.org/10.1090/S0002-9939-03-06970-3
Keywords: Periodicity, Frobenius, lattice, coin-changing
Received by editor(s): December 31, 2001
Published electronically: January 15, 2003
Communicated by: David E. Rohrlich
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society