I guess that n(k) > \( \lbrace n,n (1) 2 \rbrace \):
- n(1) = \(3 > \lbrace 1,1 (1) 2 \rbrace = 1\)
- n(2) = \(11 > \lbrace 2,2 (1) 2 \rbrace = 4\)
- n(3) > \(2 \uparrow^{7197}158386 > \lbrace 3,3 (1) 2 \rbrace = 3 \uparrow\uparrow\uparrow 3\)
Since n(k) grows faster than \(f_{\omega^\omega}(n)\), n(4) > \(\lbrace 4,4,4,4 \rbrace\) Ikosarakt1 (talk) 11:44, January 7, 2013 (UTC)
- That isn't necessarily true. While n(k) may grow faster than fωω for all sufficiently large inputs, it doesn't mean n(4) must be greater than (or even close to) fωω(4).
- Consider functions f and g, for example. Let f(k) = 10,000 * k and g(k) = 2k. The latter grows asymptotically faster, but g(k) doesn't exceed f(k) until k > 17.
- Another thing to note is that Friedman doesn't give an upper bound for n(4). The lower bound of AA(187196(1) is a lot smaller than fωω(4) > {4, 4, 4, 4, 4, 4}. --Ixfd64 (talk) 07:45, January 9, 2013 (UTC)
However, \( \lbrace n,n (1) 2 \rbrace \) has the same growth rate as \( f_{\omega^\omega} \), but n(k) overtakes the first function at k=3. Since n(k) grows faster than \( \lbrace n,n (1) 2 \rbrace \), it is quite possible that n(k) is ahead \( \lbrace n,n (1) 2 \rbrace \) for all k>=3. Ikosarakt1 (talk) 14:22, January 9, 2013 (UTC)
Recursion in this system[]
According to Friedman's results, the power of this subsequence system is BAN/BEAN's linear arrays, but how to simulate the pattern of constructing string that, say, will be {3,3,3,3,3} terms long?
Also, can we make a good bounds for n(5), n(6), n(7), etc...? And I still believe that n(k) really can be bounded below by {3,m (1) 2} (for n>2), but the proof would be nice. Ikosarakt1 (talk ^ contribs) 09:25, June 29, 2013 (UTC)
Growth rate[]
Is it possible that it grows as fast as \(f_{\omega^\omega}(f_{\omega^\omega}(n))\)? Clarrity (talk) 07:33, February 25, 2018 (UTC)
Possible extension[]
For k>1, define a k-Friedman string in the same way as in the article, except that no block of letters xi, ..., xki is a substring of any block xj, ..., xkj for j>i. (Note that 2-Friedman strings are equivalent to the original definition)
For example, 1112222222221 is a 3-Friedman string with alphabet {1,2}, and there could possibly be longer 3-Friedman strings with the same alphabet. However, I don't have proof that they have to be finite C7X (talk) 16:19, 30 November 2020 (UTC)
Upper bound of n(3)[]
Where is the source of \(n(3)<A(A(5))\)? This would be a very rare upper bound for problems like "largest length of ...". {hyp/^,cos} (talk) 16:27, 3 October 2021 (UTC)
n(2) confusion[]
The article claims that n(2) = 11. However, the sequence 1122221212121 is a valid sequence, and it has length 13. To show that it is a valid sequence, let's list all the blocks:
B1 = 11, B2 = 122, B3 = 2222, B4 = 22212, B5 = 221212, B6 = 2121212
If any of these blocks Bi is a subsequence of a later block Bj, then since the length of Bi is i+1 and the length of Bj is j+1>i+1, Bi will be a proper subsequence of Bj. Furthermore, i+1 is at least 2. Bi is not a proper subsequence of any block Bj with j<=i, because its length i+1 is at least the length j+1 of Bj, so for each i, Bi is a subsequence of a later block Bj iff it is a proper subsequence with length at least 2 of any block at all. So let's list the proper subsequences (PSes) of each block that have length at least 2, and see if any of the blocks are on this list:
PSes of B1: none
PSes of B2: 12, 22
PSes of B3: 22, 22, 22, 222, 222
PSes of B4: 22, 22, 21, 12, 222, 221, 212, 2221, 2212
PSes of B5: 22, 21, 12, 21, 12, 221, 212, 121, 212, 2212, 2121, 1212, 22121, 21212
PSes of B6: 21, 12, 21, 12, 21, 12, 212, 121, 212, 121, 212, 2121, 1212, 2121, 1212, 21212, 12121, 21212, 212121, 121212
We can easily check that B1 = 11 is not on this list (we only need to check the length 2 sequences on the lists, since sequences of other lengths are automatically different from B1). Similarly, we can check that B2 = 122 is not on the list, this time we only need to check the length 3 sequences. Then we can check that B3 = 2222 isn't there, and neither is B4, B5 or B6. Since there are no other blocks in the sequence 1122221212121, this means that no block of the sequence is a subsequence of a later block, and the sequence only contains two different symbols, so 1122221212121 is one of the sequences considered in calculation of n(2). Then n(2) is by definition greater than or equal to its length, which is 13. But n(2) >= 13 contradicts the claim in the article that n(2) = 11. Can someone edit the article to fix this, or tell me what is wrong with the sequence 1122221212121?
Rachel6174 (talk) 17:52, 9 August 2023 (UTC)
- Nevermind, apparently Friedman's definition allows gaps between terms of the subsequence, so e.g. subsequences of 121 with length 2 are 12, 21, 11 even though getting 11 requires skipping the 2 in the middle. That should be clarified in the article, with something like this: "In this context, a subsequence may contain gaps. Specifically, (xm)2im=i is a subsequence of (xm)2jm=j iff there exists a strictly increasing sequence (km)im=0 such that j<=k0 and ki<=2j and for all 0<=m<=i, xi+m=xkm".
- It would be interesting to see whether n' is a total function N->N, if it's defined the same way as n but with the usual definition of subsequence (in terms of the above definition, the usual definition would have the additional requirement that km=k0+m, which ensures there are no gaps).
- Rachel6174 (talk) 07:20, 10 August 2023 (UTC)