Long finite sequences

• Published in 1998
• Added on 2012-04-24

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

• http://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf

Other information

BibTeX entry

@article{Friedman1998,
	key = {Friedman1998},
	type = {article},
	title = {Long finite sequences},
	author = {Friedman, Harvey M},
	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 = {},
	date_added = {2012-04-24},
	date_published = {1998-04-10},
	urls = {http://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf},
	collections = {},
	url = {http://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf},
	urldate = {2012-04-24},
	pages = {1--50},
	year = 1998
}