Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Constructing $ k$-radius sequences


Authors: Simon R. Blackburn and James F. McKee
Journal: Math. Comp. 81 (2012), 2439-2459
MSC (2010): Primary 94A55
Published electronically: August 2, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An $ n$-ary $ k$-radius sequence is a finite sequence of elements taken from an alphabet of size $ n$ such that any two distinct elements of the alphabet occur within distance $ k$ of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc to model a caching strategy for computing certain functions on large data sets such as medical images. Let $ f_k(n)$ be the shortest length of any $ k$-radius sequence. We improve on earlier estimates for $ f_k(n)$ by using tilings and logarithms. The main result is that $ f_k(n)\sim \frac{1}{k}\binom{n}{2}$ as $ n\rightarrow\infty$ whenever there exists a tiling of $ \mathbb{Z}^{\pi(k)}$ by a certain cluster of $ k$ hypercubes. In particular this result holds for infinitely many $ k$, including all $ k\le 194$ and all $ k$ such that $ k+1$ or $ 2k+1$ is prime. For certain $ k$, in particular when $ 2k+1$ is prime, we get a sharper error term using the theory of logarithms.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 94A55

Retrieve articles in all journals with MSC (2010): 94A55


Additional Information

Simon R. Blackburn
Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX, United Kingdom
Email: s.blackburn@rhul.ac.uk

James F. McKee
Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX, United Kingdom
Email: james.mckee@rhul.ac.uk

DOI: http://dx.doi.org/10.1090/S0025-5718-2011-02510-X
PII: S 0025-5718(2011)02510-X
Received by editor(s): August 5, 2010
Received by editor(s) in revised form: December 17, 2010
Published electronically: August 2, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.