Interesting Esoterica

Long finite sequences

Article by Friedman, Harvey M
  • Published in 1998
  • Added on
Let k be a positive integer. There is a longest finite sequence x1,...,xn in k letters in which no consecutive block xi,...,x2i is a subsequence of any other consecutive block xj,...,x2j. Let n(k) be this longest length. We prove that n(1) = 3, n(2) = 11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackerman hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a particularly elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3).

Links

Other information

pages
1--50

BibTeX entry

@article{Friedman1998,
	title = {Long finite sequences},
	author = {Friedman, Harvey M},
	url = {http://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf},
	urldate = {2012-04-24},
	abstract = {Let k be a positive integer. There is a longest finite sequence x1,...,xn in k letters in which no consecutive block xi,...,x2i is a subsequence of any other consecutive block xj,...,x2j. Let n(k) be this longest length. We prove that n(1) = 3, n(2) = 11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackerman hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a particularly elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3).},
	comment = {},
	pages = {1--50},
	year = 1998,
	collections = {}
}