When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:
A 3-free set is a set with no arithmetic progressions of length 3. Large 3-free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n1-o(1) but there cannot be such sets of size &Omega(n) (slight tighter results are known).
I was finishing up a paper on large 3-free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3-free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):
The known algorithm uses that there are 3-free sets of {1,...,n} of size n{1-o(1)}. Improvements to the current constructions of large 3-free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to beActually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on- some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?
I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.
Unlike the case of P vs. NP, an article about 3-free sets would have a wider audience if it had applications for matrix multiplication. It would likely be quoted far more often, contributing to your reputation. This may not be why you got interested in a problem, but for many it would be a nice bonus.
ReplyDeleteYes, I can imagine you do not have a rooting interest in whether larger 3-free sets exist or not. But wouldn't you have at least a slight rooting interest that the question is relevant to something else?
ReplyDelete"P\ne NP (better crypto)?"
ReplyDeleteShame, Bill: P != NP doesn't imply OWF exist.
A131741
ReplyDeletea(n) is least prime (not already in list) such that no 3-term subset forms an arithmetic progression.
2, 3, 5, 11, 13, 29, 31, 37, 41, 67, 73, 83, 89, 101, 107, 127, 139, 157, 179, 193, 227, 233, 263, 271, 281, 307, 331, 337, 379, 389, 397, 401, 409, 431, 433, 467, 491, 499, 509, 563, 571, 613, 641, 647, 743, 769, 809, 823, 883, 887, 907, 937, 983, 1009, 1021
COMMENT
a(n) is the smallest prime such that there is no i < j < n with a(n) - a(j) = a(j) - a(i).
EXAMPLE
Table showing derivation of first 10 values.
n a(n) comment
1 2
2 3
3 5
4 11 a(4) can't be 7 because (3,5,7) is in arithmetic progression.
5 13
6 29 can't be 17 because (5,11,17); can't be 19 because (3,11,19); can't be 23 because (3,13,23)
7 31
8 37
9 41
10 67 not 43 as (31,37,43); not 47 as (11,29,47); not 53 as (29,41,53); not 59 as (13,31,59); not 61 as (13,37,61)
MATHEMATICA
f[l_List] := Block[{c, f = 0}, c = If[l == {}, 0, l[[ -1]]]; While[f == 0, c = NextPrime[c]; If[Intersection[l, l - (c - l)] == {}, f = 1]; ]; Append[l, c] ]; Nest[f, {}, 100]
CROSSREFS
Cf. A000040, A065825.
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post (jvospost2(AT)yahoo.com), Oct 04 2007
EXTENSIONS
More terms and program from Ray Chandler