Fine-Wilf graphs and the generalized Fine-Wilf theorem

Details Fine-Wilf graphs and the generalized Fine-Wilf theorem Fine-Wilf graphs and the generalized Fine-Wilf theorem

2009-06-09

arxiv.org/abs/0906.1780v1

Mathematics

Combinatorics

Scientific paper

In 1962, R. C. Lyndon and M. P. Shutzenberger established that for any positive integers r and s, any sequence of length at least r+s that is both r-periodic and s-periodic is then (r,s)-periodic. Shortly thereafter (1965), N. J. Fine and H. S. Wilf proved that for any positive integers r and s, if a is an infinite seqeunce of period r and b is an infinite sequence of period s such that a_i=b_i for all i with 1\le i\le r+s-(r,s), then a=b. This is equivalent to the following result, which is commonly referred to as the Fine-Wilf theorem: for any positive integers r and s, if w is a finite sequence that is both r-periodic and s-periodic, and |w|\ge r+s-(r,s), then w is (r,s)-periodic. The Fine-Wilf theorem was generalized to finite sequences with three periods by M. G. Castelli, F. Mignosi, and A. Restivo, and in general by J. Justin, and even more broadly by R. Tijdeman and L. Zamboni. They introduced functions f and fw from the set of all sequences of nonnegative integers to the set of positive integers, and they proved that for a sequence p=(p_1,p_2,...,p_n), a finite sequence w with periods p_i, i=1,2,..., n and length at least fw(p) must be (p)-periodic as well, and that there exists a sequence w of length fw(p)-1 that is p_i-periodic for all i, but not (p)-periodic. In this paper, we follow ideas introduced by S. Constantinescu and L. Ilie to obtain an alternative formulation of f and fw, and we establish important properties of f and fw, obtaining in particular new upper and lower bounds for each. We also begin an investigation of Fine-Wilf graphs for arbitrary finite sequences.

Affiliated with

Also associated with

No associations

Rating

Fine-Wilf graphs and the generalized Fine-Wilf theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fine-Wilf graphs and the generalized Fine-Wilf theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fine-Wilf graphs and the generalized Fine-Wilf theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65436