![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyIn truth, I don't think the fact that this is in Spanish would be a real problem, were it not for the fact that he was looking at the problem slightly differently from us.
Since these two conjectures are ones we've salvaged and proved, this is going to basically just going to be a review of stuff we've already done. But it may make explicit some stuff I've left implicit before.
Note on notation: While I'm using Arias's ||n|| notation, I'm still going to use 'g' and 'L' to mean the things I have before... Arias uses these to mean rather different things. (What I call 'L', Arias calls 'g', and what he calls 'L' is something we haven't had any use for. I don't think he gave a name to what we call 'g'?)
...actually, now that I run this through Google Translate (annoyance: accented chars don't copy/paste correctly from the PDF, need to enter those manually), and can read the motivation for the conjectures, the mistakes make a little more sense. ("The mistakes" that I've seen so far being basically that even though he noted that ||3n|| and ||n||+3 aren't always equal, he didn't really take this to heart, and conjectured several things that would require this to be true.)
He was looking at the highest numbers writable with n 1's, and the largest few *do* obey this law, as I showed[0]. Interesting to see the different perspectives we originally came at the problem from. When I was doing my original "enormous tree" approach, I honestly didn't even think to look at the actual data, since I already had the method...
Anyway! Let's get on with this. I'm going to consider these two together. These are coming mostly straight from Google Translate.
Conjecture 3. There are three transfinite sequences of rational numbers (aα)(α<ξ), (bα)(α<ξ), (cα)(α<ξ), such that the (greater) numbers of complexity 3n (respectively 3n+1, 3n+2) are the (first) natural numbers contained in the sequence (3naα) (resp. (3nbα), (3ncα)).
ξ is an infinite countable ordinal such that ωξ = ξ.
Conjecture 4. The three sequences are decreasing. The denominators of each term of a_α, b_α, or c_α are powers of 3.
Status: OK. So. Before I point out why it's false as written, I'd like to reformulate conjecture 3 a little. As he wrote it, it bugs me a little. First thing I'd like to do is say, we should replace "3n+1" with "3n+4". In this context, {0,2,4} is a much more natural set of representatives for Z/(3) than {0,1,2}. This excludes the number 1 from consideration - which it should. 1 is a special case. Similarly, it bugs me that he used 3^n, 3^n, 3^n for the multipliers, rather than 3^n, 4*3^(n-1) [sticking with his use of 3n+1 instead of 3n+4 here], 2*3^n.
The second thing I'd like to do is, as long as I'm going to point out why this conjecture is false, let's turn it into a bolder conjecture!
Hypothetical bolder version of conjecture 3: There is an transfinite sequence of rational numbers (aα)(α<ξ) such that the (greater) numbers of complexity n are the (first) natural numbers contained in the sequence (g(n)aα). Etc.
Of course, I'm going to guess that the reason that he didn't make this hypothetical bolder version, is that it's false even for the low defects Arias was looking at. (Though back when I was programming this, due to a bug in my program, it took me quite a while to notice this!) Why? Suppose it were true. Then consider the number 82. ||82||=13, and g(13)=4*3^3=108. So the term in the sequence giving you 82 would be 82/108=41/54. But 54=2*3^3=g(11), so 41=g(11)*(41/54) would show up in the sequence for g(11), meaning 41 would be writable with 11 ones. Which it isn't; ||41||=12. The problem is that ||2*41|| isn't equal to ||41||+2. (Note - this is not the minimal counterexample; that would be 2*23=46. But it is the counterexample of minimal defect; 23 and 46 have way higher defect than what Arias was looking at.)
Splitting it into three sequences avoids this problem... but unfortunately there's no way to avoid the problem that ||3n|| isn't always equal to ||n||+3. As written, the conjecture is false. Suppose it were true and consider 321. ||321||=18, 18=3*6, so 321/3^6=107/3^5 would lie in the sequence of aα's. But then 107=3^5*(107/3^5) would have to be writable with 15 ones - which, again, it isn't; ||107||=16. In general, if true, this conjecture would imply that ||3n||=||n||+3 for all n. As I said above - he may have noted that this point is false, but he didn't really take the lesson to heart, evidently[3].
Before we get to salvaging this, let's actually look at conjecture 4. The second part of it, about the denominators being powers of 3, I don't understand why he put that there, because that's true by definition. (Though it would be modified to "power of 3, two times power of 3, or four times power of 3" if we made the modifications above.) Anything whose denominator wasn't a power of 3 could be safely excluded from the sequence. So, I'm just going to ignore that.
But OK, how can we salvage this? The whole idea of this sequence where you can multiply by a power of 3 (or perhaps a 2*3^n or 4*3^n) through to find what numbers have a given complexity, is simply wrong. Get rid of that and you're just left saying that a countable set can be enumerated by an ordinal, which doesn't say anything at all. Fortunately, we can turn it nontrivial again by combining it with #4: The requirement that the sequence be decreasing. Then what you're saying is, this set (or these sets) are reverse well-ordered. Though, I see more than one possible way to salvage this... let me list three of them.
Salvage of 3 and 4, version 1: The sets {n/g(||n||) : ||n||=0 (mod 3)}, {n/g(||n||) : ||n||=2 (mod 3)}, and {n/g(||n||) : ||n||=1 (mod 3), n≠1}, are reverse well-ordered.
(OK, excluding n=1 doesn't actually do anything there, it works perfectly well with 1 included, I'm just excluding it out of principle. :) )
This is closest to Arias's version, in that it's split in three; note that changing his 3⌊||n||/3⌋ to a g(||n||) doesn't affect anything, as it's just a constant factor applied to each of the three sets. Indeed, instead of changing to g(||n||), we could also just get rid of the floors there and use 3||n||/3. Same statement.
But hey, since ||2n||≠||n||+2 is no longer really a problem for us, why split in three at all? Let's merge it all back into one! The resulting statement will be equivalent - well-ordering is preserved under subsets and under finite unions.
Salvage of 3 and 4, version 2: The set {n/g(||n||) : n∈N} is reverse well-ordered.
But like I said, instead of g(||n||) in the denominator in the first version, we could also put 3||n||/3... let's merge those sequences, instead. It's equivalent, yes, but let's do it anyway.
Salvage of 3 and 4, version 3: The set {n/3||n||/3 : n∈N} is reverse well-ordered.
Well, these statements are all equivalent, and as we recently proved, they're all true.
I could include a version 4, based on 3⌊||n||/3⌋ like Arias did, but I see no reason to do so. Why include version 2? Because it's the most natural way to state it, I think, considering the problem. But then why include version 3? Ah, well, that would be because that's how we actually proved it. :) We've been talking about the set of defects being well-ordered, but if you haven't noticed, you take d(n)=||n||-3log_3(n), you raise 31/3 to that power and you take the reciprocal (reversing the order), and the notions are equivalent. Fundamentally, 3n/3 is multiplicative, whereas g(n) isn't, and that makes the former a lot easier to work with.
Somewhere along the way here I started ignoring the question of just what the (obviously countable) ordinal in question is, though. Arias called it ξ and conjectured that it satisfied ωξ=ξ. This is true as well - in fact, the order type of all five of the sets I've listed above is exactly equal to ωω. (Though equivalence here is not as obvious, and SFAICT relies on actually knowing some facts about these sets.)
Finally, to recover at least some of what Arias originally conjectured, we can note that if we stick to the split-in-three-sets version, this his idea is in fact true if we stick to indices less than ω². (That's not the absolute limit here, but I don't really think being more specific than that is worth my time, and this way it's true regardless of which of the three sets we're considering.)
ADDENDUM next day for clarity: That is to say, using the three-sequence formulation, at indices less than ω², if you multiply through the numbers you get will in fact have the appropriate complexity. And they will be in decreasing order, seeing as how you took a decreasing sequence and multiplied through by a constant.
Later ones will come... later. Then we'll be getting into ones we really haven't considered. I think you can see why I'm stopping here for now.
-Harry
[0](Actually, thought: My computations show this is true for n with D(n)≤2, but because the boundary between D(n)=2 and D(n)=3 doesn't depend on what ||n|| is mod 3, that means we can rewrite that statement more simply, as follows: If n>g(||n||)/3, then ||3n||=||n||+3. (And thus ||3^k*n||=||n||+3k.)
[3]This *is* the minimal counterexample; the counterexample of minimal defect would be 683*3=2049.
Since these two conjectures are ones we've salvaged and proved, this is going to basically just going to be a review of stuff we've already done. But it may make explicit some stuff I've left implicit before.
Note on notation: While I'm using Arias's ||n|| notation, I'm still going to use 'g' and 'L' to mean the things I have before... Arias uses these to mean rather different things. (What I call 'L', Arias calls 'g', and what he calls 'L' is something we haven't had any use for. I don't think he gave a name to what we call 'g'?)
...actually, now that I run this through Google Translate (annoyance: accented chars don't copy/paste correctly from the PDF, need to enter those manually), and can read the motivation for the conjectures, the mistakes make a little more sense. ("The mistakes" that I've seen so far being basically that even though he noted that ||3n|| and ||n||+3 aren't always equal, he didn't really take this to heart, and conjectured several things that would require this to be true.)
He was looking at the highest numbers writable with n 1's, and the largest few *do* obey this law, as I showed[0]. Interesting to see the different perspectives we originally came at the problem from. When I was doing my original "enormous tree" approach, I honestly didn't even think to look at the actual data, since I already had the method...
Anyway! Let's get on with this. I'm going to consider these two together. These are coming mostly straight from Google Translate.
Conjecture 3. There are three transfinite sequences of rational numbers (aα)(α<ξ), (bα)(α<ξ), (cα)(α<ξ), such that the (greater) numbers of complexity 3n (respectively 3n+1, 3n+2) are the (first) natural numbers contained in the sequence (3naα) (resp. (3nbα), (3ncα)).
ξ is an infinite countable ordinal such that ωξ = ξ.
Conjecture 4. The three sequences are decreasing. The denominators of each term of a_α, b_α, or c_α are powers of 3.
Status: OK. So. Before I point out why it's false as written, I'd like to reformulate conjecture 3 a little. As he wrote it, it bugs me a little. First thing I'd like to do is say, we should replace "3n+1" with "3n+4". In this context, {0,2,4} is a much more natural set of representatives for Z/(3) than {0,1,2}. This excludes the number 1 from consideration - which it should. 1 is a special case. Similarly, it bugs me that he used 3^n, 3^n, 3^n for the multipliers, rather than 3^n, 4*3^(n-1) [sticking with his use of 3n+1 instead of 3n+4 here], 2*3^n.
The second thing I'd like to do is, as long as I'm going to point out why this conjecture is false, let's turn it into a bolder conjecture!
Hypothetical bolder version of conjecture 3: There is an transfinite sequence of rational numbers (aα)(α<ξ) such that the (greater) numbers of complexity n are the (first) natural numbers contained in the sequence (g(n)aα). Etc.
Of course, I'm going to guess that the reason that he didn't make this hypothetical bolder version, is that it's false even for the low defects Arias was looking at. (Though back when I was programming this, due to a bug in my program, it took me quite a while to notice this!) Why? Suppose it were true. Then consider the number 82. ||82||=13, and g(13)=4*3^3=108. So the term in the sequence giving you 82 would be 82/108=41/54. But 54=2*3^3=g(11), so 41=g(11)*(41/54) would show up in the sequence for g(11), meaning 41 would be writable with 11 ones. Which it isn't; ||41||=12. The problem is that ||2*41|| isn't equal to ||41||+2. (Note - this is not the minimal counterexample; that would be 2*23=46. But it is the counterexample of minimal defect; 23 and 46 have way higher defect than what Arias was looking at.)
Splitting it into three sequences avoids this problem... but unfortunately there's no way to avoid the problem that ||3n|| isn't always equal to ||n||+3. As written, the conjecture is false. Suppose it were true and consider 321. ||321||=18, 18=3*6, so 321/3^6=107/3^5 would lie in the sequence of aα's. But then 107=3^5*(107/3^5) would have to be writable with 15 ones - which, again, it isn't; ||107||=16. In general, if true, this conjecture would imply that ||3n||=||n||+3 for all n. As I said above - he may have noted that this point is false, but he didn't really take the lesson to heart, evidently[3].
Before we get to salvaging this, let's actually look at conjecture 4. The second part of it, about the denominators being powers of 3, I don't understand why he put that there, because that's true by definition. (Though it would be modified to "power of 3, two times power of 3, or four times power of 3" if we made the modifications above.) Anything whose denominator wasn't a power of 3 could be safely excluded from the sequence. So, I'm just going to ignore that.
But OK, how can we salvage this? The whole idea of this sequence where you can multiply by a power of 3 (or perhaps a 2*3^n or 4*3^n) through to find what numbers have a given complexity, is simply wrong. Get rid of that and you're just left saying that a countable set can be enumerated by an ordinal, which doesn't say anything at all. Fortunately, we can turn it nontrivial again by combining it with #4: The requirement that the sequence be decreasing. Then what you're saying is, this set (or these sets) are reverse well-ordered. Though, I see more than one possible way to salvage this... let me list three of them.
Salvage of 3 and 4, version 1: The sets {n/g(||n||) : ||n||=0 (mod 3)}, {n/g(||n||) : ||n||=2 (mod 3)}, and {n/g(||n||) : ||n||=1 (mod 3), n≠1}, are reverse well-ordered.
(OK, excluding n=1 doesn't actually do anything there, it works perfectly well with 1 included, I'm just excluding it out of principle. :) )
This is closest to Arias's version, in that it's split in three; note that changing his 3⌊||n||/3⌋ to a g(||n||) doesn't affect anything, as it's just a constant factor applied to each of the three sets. Indeed, instead of changing to g(||n||), we could also just get rid of the floors there and use 3||n||/3. Same statement.
But hey, since ||2n||≠||n||+2 is no longer really a problem for us, why split in three at all? Let's merge it all back into one! The resulting statement will be equivalent - well-ordering is preserved under subsets and under finite unions.
Salvage of 3 and 4, version 2: The set {n/g(||n||) : n∈N} is reverse well-ordered.
But like I said, instead of g(||n||) in the denominator in the first version, we could also put 3||n||/3... let's merge those sequences, instead. It's equivalent, yes, but let's do it anyway.
Salvage of 3 and 4, version 3: The set {n/3||n||/3 : n∈N} is reverse well-ordered.
Well, these statements are all equivalent, and as we recently proved, they're all true.
I could include a version 4, based on 3⌊||n||/3⌋ like Arias did, but I see no reason to do so. Why include version 2? Because it's the most natural way to state it, I think, considering the problem. But then why include version 3? Ah, well, that would be because that's how we actually proved it. :) We've been talking about the set of defects being well-ordered, but if you haven't noticed, you take d(n)=||n||-3log_3(n), you raise 31/3 to that power and you take the reciprocal (reversing the order), and the notions are equivalent. Fundamentally, 3n/3 is multiplicative, whereas g(n) isn't, and that makes the former a lot easier to work with.
Somewhere along the way here I started ignoring the question of just what the (obviously countable) ordinal in question is, though. Arias called it ξ and conjectured that it satisfied ωξ=ξ. This is true as well - in fact, the order type of all five of the sets I've listed above is exactly equal to ωω. (Though equivalence here is not as obvious, and SFAICT relies on actually knowing some facts about these sets.)
Finally, to recover at least some of what Arias originally conjectured, we can note that if we stick to the split-in-three-sets version, this his idea is in fact true if we stick to indices less than ω². (That's not the absolute limit here, but I don't really think being more specific than that is worth my time, and this way it's true regardless of which of the three sets we're considering.)
ADDENDUM next day for clarity: That is to say, using the three-sequence formulation, at indices less than ω², if you multiply through the numbers you get will in fact have the appropriate complexity. And they will be in decreasing order, seeing as how you took a decreasing sequence and multiplied through by a constant.
Later ones will come... later. Then we'll be getting into ones we really haven't considered. I think you can see why I'm stopping here for now.
-Harry
[0](Actually, thought: My computations show this is true for n with D(n)≤2, but because the boundary between D(n)=2 and D(n)=3 doesn't depend on what ||n|| is mod 3, that means we can rewrite that statement more simply, as follows: If n>g(||n||)/3, then ||3n||=||n||+3. (And thus ||3^k*n||=||n||+3k.)
[3]This *is* the minimal counterexample; the counterexample of minimal defect would be 683*3=2049.
