Problem statement
Jul. 4th, 2010 06:22 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyOK, guys, time to finally write this. I've written repeatedly about the ridiculous tedious computation I did to classify n with d(n)<21d(2); I've mentioned I started writing a program to do it automatically for d(n)<18d(2), but I never finished it; I've said about how, despite this computation being *almost* algorithmic, I haven't been able to figure out how to automate the process in general. And I've said I would post here a fulls tatement of just what it was that I was trying to automate and ask if anyone has any ideas how this can be fully algorithmized. So... time to actually do that.
OK! So. We fix some k, we want to determine all n with d(n)<k. (I'll call this set A_k.) Or perhaps ≤k - this is a straightforward modification, you can basically just change all the strict inequalities to nonstrict inequalities. Josh proved we can build up a superset of A_k inductively. Let's pick a step size, α. Now, for proving lots of the stuff we have, we can take any α<1. Indeed, for lots of the stuff we have proved, it is crucial that we can take α arbitrarily close to 1! However, in those cases, it suffices to just look at some superset of A_k; here we're trying to determine A_k itself, to determine the complexity of our candidates and filter out the ones that don't belong. So α<1 isn't going to be good enough. We're going to need α<1/2. But in fact, let's impose an even stricter requirement - α≤d(2). The more general version is harder to explain, and hey, if you can get as far as actually automating this, does it really matter if your step size is small? Passing to that general case isn't the hard part, anyway. This explanation will contain all the important ideas.
Note: Allowing α=d(2) requires we be using strict inequalities; if for some reason you're taking α<d(2), you can go ahead and use nonstrict; why exclude the endpoint? The reason I'm using strict inequalities in the first place is because I wanted to use as large a step size as I could, I didn't want to just approach d(2) arbitrarily closely. Note that using α=d(2), you actually get the endpoint as a freebie - say you go up to A_(kd(2)), well, what has defect of exactly kd(2)? The only possibility is 2^k times powers of 3, so all you have to do is check if those do in fact have the expected complexity.
Actually, from here on out, to make things even simpler, I'm just going to go ahead and assume α=d(2). Smaller steps could be useful in some cases, but no need to make things more complicated right now.
OK. Let's suppose you already know A_d(2) - well, OK, this is just the set of non-one powers of 3, and ||3*3^k||=3+3k. And A_2d(2), well that just adds in numbers of the form 2*3^k, and ||2*3^k||=2+3k.
So, let's say you've got A_d(2), A_2d(2), ..., A_nd(2), and you want to determine A_(n+1)d(2). Here we're assuming n≥2.
Then, every element of A_(n+1)d(2) has one of the following forms:
(Note, here I am using the fact that step size is d(2); if it were larger, I'd have to generalize this a bit.)
1. It's a member of A_nα. (I guess this doesn't need to be separately included, but may as well.)
2. It's a product a*b, with a∈A_id(2), b∈A_jd(2), and i+j=n+2. (2≤i,j≤n, to prevent stupid stuff.)
3. It's a sum a+b, where a∈A_nd(2), and b<2*3^((n+1)d(2)/3). We can assume that b cannot be written most efficiently as a sum. Note that this excludes in particular 2, 3, 4, and 5 from consideration as possible b's, so there's quite a gap between when 1 becomes a possible b (immediately) and when the next number, 6, becomes a possible b. Also note, if you're going that high, that just because something can be written most efficiently as a product, doesn't mean it can't be written most efficiently as a sum - you may think of 10 as 2*5, but 1+9 is just as good, so 10 is perfectly excludable.
4. It's a power of 3 times something of form 3.
5. It's a power of 3 times something in the set {1,2,3,5}. Note that we know how to compute the complexity of any multiple of 3 times one of these - they're exactly what you expect; ||1||=1, ||3*3^k||=3+3k, ||2*3^k||=2+3k, ||5*3^k||=5+3k.
Now... this is enough if all you're interested in is finding a superset of A_(n+1)d(2). But we want more than that. So. How can we determine the complexity of these things, and powers of 3 times them?
If it's of form 1, we've already determined it. Yay. And if it's of form 4, I've listed it above.
Now the thing is, if it's of form 2 or 3, it still might already be in A_nd(2). In this case, well, it is whatever we've already determined it to be. But if it's *not* in A_nd(2), then we have the following:
If it's of form 2, written as a*b, and not already in A_nd(2), then the complexity is in fact just ||a||+||b||.
If it's of form 3 or 4, written as 3^k*(a+b)... uh, well, I don't know how to handle that in general. Fortunately, as I pointed out above, for quite a while we only have to deal with the case b=1. So that's all I intend to automate - +6s and stuff, I can do by hand if it becomes relevant; don't worry about that. (Well, if I can do them at all. But that's another matter.)
So, if it's of form 3 or 4, written as 3^k*(a+1), and not already in A_nd(2), then the complexity is in fact just ||a||+3k+1.
So you can determine the complexity (ignoring +6s and stuff anyway), you can determine the defect, you can see what stays in and what gets cut out.
So what's the problem, anyway? This all sounds straightforward enough, right? Well, no. The big problem is data representation: How do you represent these sets? Let's throw out powers of 3 for now - let's assume you're representing things as (base sets * powers of 3). How do you represent these base sets? A_d(2), A_2d(2), these are finite sets once you throw out the powers of 3. But to proceed with the induction, well, you have to put those powers of 3 back in and add 1. (And then multiply by powers of 3 again, but we're ignoring those, recall.) And that's not a finite set.
Let's write things in ternary. We've got this number, 2. If we multiply by powers of 3 and add 1, we get the ternary regular expression 20*1 - well, if the power of 3 in question isn't 0, if it is we get 10. OK, so as a regular expression, 20*1|10.
So why not just do that? Think of things like that? After all, we take 20*1 and we multiply that by powers of 3 and add 1, well we just get 20*10*1, or near enough right? That's what my unfinished program did - these cases of a0*b0*c0*d etc aren't too hard to handle. But the thing is, once we have these infinite families, we have to consider products of them. What happens when we multiply 20*1 by 20*1? Or by 10*1? What about when there's three factors? Or worse yet, you multiply two of these together, then multipy by powers of 3 and add one, and then multiply by a third thing?
We need some way of representing "ternary patterns", or whatever you want to call these families, versatile enough to handle this, but still workable. What do we need? Well, obviously for a start, we need to be able to implement multiplication, and "multiply by powers of 3 and add one."
But we need to be able to do more than that - we need to be able to specialize these things. We need to be able to, given such a family and a cutoff defect, compute which elements have defect less than that cutoff; and more importantly, we need to be able to represent the resulting set somehow! Perhaps as a finite union of more directly represented sets, but somehow.
Now, assuming we're dealing with things not already in A_nd(2), the defect increases strictly monotonically with the parameters, but the exact order can vary. In the simplest case, say something like (2*3^m+1)3^k+1, it's lexicographic, so we'll need to be able to specialize to pairs (m,k) pulled from some lexicographically downwardly-closed set. More generally, it may not be - say we look at (2*3^m+1)(2*3^k+1), that's symmetric in m and k, it can't be lexicographic; turns out whichever one is smaller is more important. But we still need to be able to specialize.
What's more, suppose we want to write down the complexity of these things explicitly. Then we need to be able to look at these infinite families we've produced and determine which elements are already in A_nd(2), as these will be exceptions to the general rule. So we need then of taking one of these patterns, and set-theoretically subtracting others from it, to excise these exceptions.
So... we've got a data representation problem. I'll admit I haven't banged my head against this as much as I probably could have, but still, I don't think I can figure this out myself. Any ideas, guys?
(I *think* I've pretty much covered everything, but perhaps not. Do ask if anything's unclear...)
-Harry
OK! So. We fix some k, we want to determine all n with d(n)<k. (I'll call this set A_k.) Or perhaps ≤k - this is a straightforward modification, you can basically just change all the strict inequalities to nonstrict inequalities. Josh proved we can build up a superset of A_k inductively. Let's pick a step size, α. Now, for proving lots of the stuff we have, we can take any α<1. Indeed, for lots of the stuff we have proved, it is crucial that we can take α arbitrarily close to 1! However, in those cases, it suffices to just look at some superset of A_k; here we're trying to determine A_k itself, to determine the complexity of our candidates and filter out the ones that don't belong. So α<1 isn't going to be good enough. We're going to need α<1/2. But in fact, let's impose an even stricter requirement - α≤d(2). The more general version is harder to explain, and hey, if you can get as far as actually automating this, does it really matter if your step size is small? Passing to that general case isn't the hard part, anyway. This explanation will contain all the important ideas.
Note: Allowing α=d(2) requires we be using strict inequalities; if for some reason you're taking α<d(2), you can go ahead and use nonstrict; why exclude the endpoint? The reason I'm using strict inequalities in the first place is because I wanted to use as large a step size as I could, I didn't want to just approach d(2) arbitrarily closely. Note that using α=d(2), you actually get the endpoint as a freebie - say you go up to A_(kd(2)), well, what has defect of exactly kd(2)? The only possibility is 2^k times powers of 3, so all you have to do is check if those do in fact have the expected complexity.
Actually, from here on out, to make things even simpler, I'm just going to go ahead and assume α=d(2). Smaller steps could be useful in some cases, but no need to make things more complicated right now.
OK. Let's suppose you already know A_d(2) - well, OK, this is just the set of non-one powers of 3, and ||3*3^k||=3+3k. And A_2d(2), well that just adds in numbers of the form 2*3^k, and ||2*3^k||=2+3k.
So, let's say you've got A_d(2), A_2d(2), ..., A_nd(2), and you want to determine A_(n+1)d(2). Here we're assuming n≥2.
Then, every element of A_(n+1)d(2) has one of the following forms:
(Note, here I am using the fact that step size is d(2); if it were larger, I'd have to generalize this a bit.)
1. It's a member of A_nα. (I guess this doesn't need to be separately included, but may as well.)
2. It's a product a*b, with a∈A_id(2), b∈A_jd(2), and i+j=n+2. (2≤i,j≤n, to prevent stupid stuff.)
3. It's a sum a+b, where a∈A_nd(2), and b<2*3^((n+1)d(2)/3). We can assume that b cannot be written most efficiently as a sum. Note that this excludes in particular 2, 3, 4, and 5 from consideration as possible b's, so there's quite a gap between when 1 becomes a possible b (immediately) and when the next number, 6, becomes a possible b. Also note, if you're going that high, that just because something can be written most efficiently as a product, doesn't mean it can't be written most efficiently as a sum - you may think of 10 as 2*5, but 1+9 is just as good, so 10 is perfectly excludable.
4. It's a power of 3 times something of form 3.
5. It's a power of 3 times something in the set {1,2,3,5}. Note that we know how to compute the complexity of any multiple of 3 times one of these - they're exactly what you expect; ||1||=1, ||3*3^k||=3+3k, ||2*3^k||=2+3k, ||5*3^k||=5+3k.
Now... this is enough if all you're interested in is finding a superset of A_(n+1)d(2). But we want more than that. So. How can we determine the complexity of these things, and powers of 3 times them?
If it's of form 1, we've already determined it. Yay. And if it's of form 4, I've listed it above.
Now the thing is, if it's of form 2 or 3, it still might already be in A_nd(2). In this case, well, it is whatever we've already determined it to be. But if it's *not* in A_nd(2), then we have the following:
If it's of form 2, written as a*b, and not already in A_nd(2), then the complexity is in fact just ||a||+||b||.
If it's of form 3 or 4, written as 3^k*(a+b)... uh, well, I don't know how to handle that in general. Fortunately, as I pointed out above, for quite a while we only have to deal with the case b=1. So that's all I intend to automate - +6s and stuff, I can do by hand if it becomes relevant; don't worry about that. (Well, if I can do them at all. But that's another matter.)
So, if it's of form 3 or 4, written as 3^k*(a+1), and not already in A_nd(2), then the complexity is in fact just ||a||+3k+1.
So you can determine the complexity (ignoring +6s and stuff anyway), you can determine the defect, you can see what stays in and what gets cut out.
So what's the problem, anyway? This all sounds straightforward enough, right? Well, no. The big problem is data representation: How do you represent these sets? Let's throw out powers of 3 for now - let's assume you're representing things as (base sets * powers of 3). How do you represent these base sets? A_d(2), A_2d(2), these are finite sets once you throw out the powers of 3. But to proceed with the induction, well, you have to put those powers of 3 back in and add 1. (And then multiply by powers of 3 again, but we're ignoring those, recall.) And that's not a finite set.
Let's write things in ternary. We've got this number, 2. If we multiply by powers of 3 and add 1, we get the ternary regular expression 20*1 - well, if the power of 3 in question isn't 0, if it is we get 10. OK, so as a regular expression, 20*1|10.
So why not just do that? Think of things like that? After all, we take 20*1 and we multiply that by powers of 3 and add 1, well we just get 20*10*1, or near enough right? That's what my unfinished program did - these cases of a0*b0*c0*d etc aren't too hard to handle. But the thing is, once we have these infinite families, we have to consider products of them. What happens when we multiply 20*1 by 20*1? Or by 10*1? What about when there's three factors? Or worse yet, you multiply two of these together, then multipy by powers of 3 and add one, and then multiply by a third thing?
We need some way of representing "ternary patterns", or whatever you want to call these families, versatile enough to handle this, but still workable. What do we need? Well, obviously for a start, we need to be able to implement multiplication, and "multiply by powers of 3 and add one."
But we need to be able to do more than that - we need to be able to specialize these things. We need to be able to, given such a family and a cutoff defect, compute which elements have defect less than that cutoff; and more importantly, we need to be able to represent the resulting set somehow! Perhaps as a finite union of more directly represented sets, but somehow.
Now, assuming we're dealing with things not already in A_nd(2), the defect increases strictly monotonically with the parameters, but the exact order can vary. In the simplest case, say something like (2*3^m+1)3^k+1, it's lexicographic, so we'll need to be able to specialize to pairs (m,k) pulled from some lexicographically downwardly-closed set. More generally, it may not be - say we look at (2*3^m+1)(2*3^k+1), that's symmetric in m and k, it can't be lexicographic; turns out whichever one is smaller is more important. But we still need to be able to specialize.
What's more, suppose we want to write down the complexity of these things explicitly. Then we need to be able to look at these infinite families we've produced and determine which elements are already in A_nd(2), as these will be exceptions to the general rule. So we need then of taking one of these patterns, and set-theoretically subtracting others from it, to excise these exceptions.
So... we've got a data representation problem. I'll admit I haven't banged my head against this as much as I probably could have, but still, I don't think I can figure this out myself. Any ideas, guys?
(I *think* I've pretty much covered everything, but perhaps not. Do ask if anything's unclear...)
-Harry
