![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo, two entries ago, I discussed some variants on the Mahler-Popken problem. I'd like here to return to the original Mahler-Popken problem and discuss a different variant. Namely: What is the second-largest number we can make with k x's?
First, though, we should talk about the answer to the original problem in more detail. As before, I'm going to focus on what happens when k is sufficiently large, and how large k needs to be may depend on x.
So, as mentioned in the previous entry, to make the largest possible number from k x's, we want to group them into groups of m and then multiply them together. How large is m?
Well, m is the m that maximizes (mx)1/m. This is approximately e/x; indeed, e/x would be the maximum if we allowed m to vary continuously, but since that's not possible, m will be either the floor or the ceiling of this. The value of m changes over at the values mm-1/(m-1)m. Or, more specifically, mm-1/(m-1)m is the largest value of x where m is the group size, and (m+1)m/mm+1 is the smallest. (Throughout, I'm going to think of x as decreasing from ∞ towards 0.) As previously mentioned, at the changeover point (m+1)m/mm+1, both groups of size m and of size m+1 work.
So. When k is divisible by m, we group things into groups of m, yielding (mx)k/m. When x is on a boundary, x=(m+1)m/mm+1, then for any k sufficiently large we can make k using groups of m and m+1, yielding ((m+1)/m)k; divisibility conditions don't even come into it.
But what about when m is well-defined but k is not divisible by m? Let's say k is r mod m, 0<r<m. In this case, we'll need to use some groups of size either m+1 or m-1 to make the congruence come out right. But which one?
This is where it gets really neat. Mahler and Popken found that, if x is larger, you want to use groups of m-1; and if x is smaller, you want to use groups of m+1. The changeover point, where both give the same
result, is at
mm-1/(m-1)m ((m²-1)/m²)r
Let's denote this number by x(m,r). There's several really neat things about this:
1. Let's note that occurrence of mm-1/(m-1)m. We've already seen that quantity before, as the value where m itself changes over, from m-1 to m. And here it's what we get if we were to plug in r=0 -- which doesn't make sense, but if you plug it in anyway, that's what you get. So, the changeover point from m-1 to m is x(m,0).
2. For a fixed m, x(m,r) is monotonically decreasing in r.
So as x decreases, the congruence classes change over from using (m-1)'s to using (m+1)'s, one at a time, in order. At first, when we first hit x(m,0), when we first start using this specific value of m, all the congruence classes (other than 0, of course) are using (m-1)'s. Then we hit x(m,1), and now, the r=1 congruence class changes over. Then we hit x(m,2), and the r=2 congruence class changes over. Etc. Until... well, obviously, after x(m,m-1), all the congruence classes have changed over and are using (m+1)'s (except, once again, 0, obviously). But what happens if we plug in r=m? What's x(m,m)?
3. If we plug in r=m, we get (m+1)m/mm+1 -- the point where we change over to the next m! That is to say, x(m,m)=x(m+1,0).
In addition, for fixed m, x(m,r) is exponential in r. Like, literally exactly exponential, not approximately. Meaning that... like, say we've already divided up the positive real line based on the value of m we get, right? With the dividing points being the numbers x(m,0), for m≥1. Let's call those the major dividing points. Now we want to divide it up further based on just on the value of m, but on the more detailed eventual behavior, based on which congruence classes are using (m-1)'s or (m+1)'s. Well now we're putting additional dividing points -- let's call them "minor dividing points" -- at the values x(m,r).
Then for any two adjacent major dividing points, the minor dividing points between them are evenly spaced if use use a log scale!
I think that's really neat! :D
But OK, what about the second-largest?
Well, unfortunately, the answer there is considerably more complicated, and I'm not going to detail it all here. I'll tell you the answer when r=0. If x≥x(m,1), you want to use m groups of size m-1 (in addition to your groups of size m). If x≤x(m,m-1), you want to use m groups of size m+1. When x is inbetween, you want to use one group of size m+1 and one group of size m-1. (This is assuming m≥2. If m=1, then you make the second-highest by throwing in a group of size 2.)
It's nicely symmetric. Unfortunately the general answer is not. Here's another example where I can tell you the full answer: Say x is on a boundary, x=x(m+1,0), so you can make the largest out of groups of size m and m+1. To make the second-largest, you'll also want to throw in a group of size m+2.
(These are actually the only two cases I need to know about for the original motivation; the hard case, when m is well-defined but does not divide k, is not actually necessary for this. But I did it anyway. :P )
Anyway, like I said, I'm not going to detail the hard case here. The hard case actually needs to be divided into several subcases, depending on whether r=1, r=m-1, both (i.e. r=1 and m=2), or (the usual case) neither. I'll just say that it can involve such things as:
I'll also note that not all the changeover points are at x(m,r) for integral 0<r<m now. Now, in some cases, there can be changeover points at x(m,½) or x(m,m-½) -- meaning, yes, we can get irrational changeover points! We can also get some changeover points which are rational but can't nicely be expressed in the form x(m,r), not unless we're willing to allow r to be irrational.
There's also the issue of discontinuity. Mk(x) is necessarily continuous in x -- after all, it's the maximum of finitely many polynomials in x. Or, you know, on a graph, in order for it to switch over from one polynomial of x to another, well, the two potential maxima have to meet, and at the point where they meet both are equal, and there's no discontinuity.
But that doesn't apply for the second-largest. Because there's two ways that the second-largest could switch. One is that the current second swaps with the current third. Then yeah, they meet, they're equal, no discontinuity.
But the other way is that it swaps with the current first, becoming the largest. Then at the point where the two meet, both are equal... meaning they're both the largest. Neither is second-largest. Instead, the next-best candidate, which to either side is third, is for an instant exposed to the world as second. You have a discontinuity.
So, above I talked about "changeover points", but I should be clear it's now no longer not always a smooth changeover -- sometimes it is, but when you're considering k that's r mod m, and the changeover point under consideration is x(m,r) itself, that point will have its own special behavior that doesn't match either what's above or what's below it.
And there's one case I want to point out that's particularly weird, and that's what happens when m=2, r=1, and you look at the discontinuity at x=x(2,1)=3/2. Because this case doesn't fall under one of the possibilities I listed above. It can't even be described as group-and-multiply!
Because, you see, while mostly you want to use groups of 2, what you want to do with your remaining 3 x's isn't to make, say, one group of 3 (for a value of 3x), or three groups of 1 (for a value of x³), but rather, to use them to make x²+x. Which, again, then gets multiplied by a bunch of groups of 2.
Isn't that crazy??
Like, I can prove all this. I can definitely prove that this happens when x=3/2 and not for any other x. But I have no good heuristic explanation of it.
First, though, we should talk about the answer to the original problem in more detail. As before, I'm going to focus on what happens when k is sufficiently large, and how large k needs to be may depend on x.
So, as mentioned in the previous entry, to make the largest possible number from k x's, we want to group them into groups of m and then multiply them together. How large is m?
Well, m is the m that maximizes (mx)1/m. This is approximately e/x; indeed, e/x would be the maximum if we allowed m to vary continuously, but since that's not possible, m will be either the floor or the ceiling of this. The value of m changes over at the values mm-1/(m-1)m. Or, more specifically, mm-1/(m-1)m is the largest value of x where m is the group size, and (m+1)m/mm+1 is the smallest. (Throughout, I'm going to think of x as decreasing from ∞ towards 0.) As previously mentioned, at the changeover point (m+1)m/mm+1, both groups of size m and of size m+1 work.
So. When k is divisible by m, we group things into groups of m, yielding (mx)k/m. When x is on a boundary, x=(m+1)m/mm+1, then for any k sufficiently large we can make k using groups of m and m+1, yielding ((m+1)/m)k; divisibility conditions don't even come into it.
But what about when m is well-defined but k is not divisible by m? Let's say k is r mod m, 0<r<m. In this case, we'll need to use some groups of size either m+1 or m-1 to make the congruence come out right. But which one?
This is where it gets really neat. Mahler and Popken found that, if x is larger, you want to use groups of m-1; and if x is smaller, you want to use groups of m+1. The changeover point, where both give the same
result, is at
mm-1/(m-1)m ((m²-1)/m²)r
Let's denote this number by x(m,r). There's several really neat things about this:
1. Let's note that occurrence of mm-1/(m-1)m. We've already seen that quantity before, as the value where m itself changes over, from m-1 to m. And here it's what we get if we were to plug in r=0 -- which doesn't make sense, but if you plug it in anyway, that's what you get. So, the changeover point from m-1 to m is x(m,0).
2. For a fixed m, x(m,r) is monotonically decreasing in r.
So as x decreases, the congruence classes change over from using (m-1)'s to using (m+1)'s, one at a time, in order. At first, when we first hit x(m,0), when we first start using this specific value of m, all the congruence classes (other than 0, of course) are using (m-1)'s. Then we hit x(m,1), and now, the r=1 congruence class changes over. Then we hit x(m,2), and the r=2 congruence class changes over. Etc. Until... well, obviously, after x(m,m-1), all the congruence classes have changed over and are using (m+1)'s (except, once again, 0, obviously). But what happens if we plug in r=m? What's x(m,m)?
3. If we plug in r=m, we get (m+1)m/mm+1 -- the point where we change over to the next m! That is to say, x(m,m)=x(m+1,0).
In addition, for fixed m, x(m,r) is exponential in r. Like, literally exactly exponential, not approximately. Meaning that... like, say we've already divided up the positive real line based on the value of m we get, right? With the dividing points being the numbers x(m,0), for m≥1. Let's call those the major dividing points. Now we want to divide it up further based on just on the value of m, but on the more detailed eventual behavior, based on which congruence classes are using (m-1)'s or (m+1)'s. Well now we're putting additional dividing points -- let's call them "minor dividing points" -- at the values x(m,r).
Then for any two adjacent major dividing points, the minor dividing points between them are evenly spaced if use use a log scale!
I think that's really neat! :D
But OK, what about the second-largest?
Well, unfortunately, the answer there is considerably more complicated, and I'm not going to detail it all here. I'll tell you the answer when r=0. If x≥x(m,1), you want to use m groups of size m-1 (in addition to your groups of size m). If x≤x(m,m-1), you want to use m groups of size m+1. When x is inbetween, you want to use one group of size m+1 and one group of size m-1. (This is assuming m≥2. If m=1, then you make the second-highest by throwing in a group of size 2.)
It's nicely symmetric. Unfortunately the general answer is not. Here's another example where I can tell you the full answer: Say x is on a boundary, x=x(m+1,0), so you can make the largest out of groups of size m and m+1. To make the second-largest, you'll also want to throw in a group of size m+2.
(These are actually the only two cases I need to know about for the original motivation; the hard case, when m is well-defined but does not divide k, is not actually necessary for this. But I did it anyway. :P )
Anyway, like I said, I'm not going to detail the hard case here. The hard case actually needs to be divided into several subcases, depending on whether r=1, r=m-1, both (i.e. r=1 and m=2), or (the usual case) neither. I'll just say that it can involve such things as:
- Using 2m-r groups of size m-1
- Using m-r+1 groups of size m-1, and a group of size m+1
- Using r groups of size m+1 when this is merely the second-largest
- Using m-r groups of size m-1 when this is merely the second-largest
- Using r-2 groups of size m+1, and a group of size m+2
- Using m+r groups of size m+1
I'll also note that not all the changeover points are at x(m,r) for integral 0<r<m now. Now, in some cases, there can be changeover points at x(m,½) or x(m,m-½) -- meaning, yes, we can get irrational changeover points! We can also get some changeover points which are rational but can't nicely be expressed in the form x(m,r), not unless we're willing to allow r to be irrational.
There's also the issue of discontinuity. Mk(x) is necessarily continuous in x -- after all, it's the maximum of finitely many polynomials in x. Or, you know, on a graph, in order for it to switch over from one polynomial of x to another, well, the two potential maxima have to meet, and at the point where they meet both are equal, and there's no discontinuity.
But that doesn't apply for the second-largest. Because there's two ways that the second-largest could switch. One is that the current second swaps with the current third. Then yeah, they meet, they're equal, no discontinuity.
But the other way is that it swaps with the current first, becoming the largest. Then at the point where the two meet, both are equal... meaning they're both the largest. Neither is second-largest. Instead, the next-best candidate, which to either side is third, is for an instant exposed to the world as second. You have a discontinuity.
So, above I talked about "changeover points", but I should be clear it's now no longer not always a smooth changeover -- sometimes it is, but when you're considering k that's r mod m, and the changeover point under consideration is x(m,r) itself, that point will have its own special behavior that doesn't match either what's above or what's below it.
And there's one case I want to point out that's particularly weird, and that's what happens when m=2, r=1, and you look at the discontinuity at x=x(2,1)=3/2. Because this case doesn't fall under one of the possibilities I listed above. It can't even be described as group-and-multiply!
Because, you see, while mostly you want to use groups of 2, what you want to do with your remaining 3 x's isn't to make, say, one group of 3 (for a value of 3x), or three groups of 1 (for a value of x³), but rather, to use them to make x²+x. Which, again, then gets multiplied by a bunch of groups of 2.
Isn't that crazy??
Like, I can prove all this. I can definitely prove that this happens when x=3/2 and not for any other x. But I have no good heuristic explanation of it.
