Proving the conjecture for 53, 71, and 95: Is it possible?

[approx]

I have been trying to see how it can be proven that a power of 3 minus a power of 2 (or a power of 2 minus a power of 3) can give you every number which is not a product of 2 or 3. I just don't see how to prove it. Does it have something to do with the fact that you can get 1 as 3 minus 2?

By the way, hello, it's nice to join you all. Hope you can clarify my confusion, and thanks.

Approx

 

[D H]

approx, you triple-posted this "interesting question". You are not supposed to do this. You should have posted topic this once and once only. Moreover, this looks like homework. You didn't show any work. You are supposed to do this.

Did you read our rules when you signed up? Here they are, https://www.physicsforums.com/showthread.php?t=5374

 

[approx]

oops

sorry, i guess i didn't know you couldn't post in the different forums...
Which forum should I leave it in, and how do i remove it?
BTW, I'm teaching math at ivytech in muncie, IN. I don't have any classes or homework anymore, and won't ever again, unless I go for my pH.D. I've tried to solve this problem for a while, most recently I looked at one of the proofs that the smallest linear combination of a and b is the gcd of a and b, and tried to generalize it for exponentiation. I just wondered if anyone had a fresh outlook that could spark an idea. Sorry.

 

[Xevarion]

I think you might be able to do an inductive proof of some kind. It doesn't seem totally easy, but my first idea is to assume it's true up to $$n$$, and then try to find a way to do it for $$n+1$$ (or the next non-multiple of 2 or 3, just call the number m) by subtracting all powers of 3 from it that are less than n+1. You'll have $$m - 3^k = 2^i(3^j - 2^l)$$ or the other way around, and then hopefully you can make sure that for at least one $$k$$, you'll have a value of $$i$$ and a sign that will allow you to get $$m$$ in the desired form.

Anyway it's just an idea. This problem doesn't seem trivial.

 

[approx]

Ok, so if m is relatively prime to 6, then m-3^k will be even and relatively prime to 3, then we can divide out 2^i to get some number, smaller than m, which we can already represent as (3^j-2^l)? But then we get m = (2^i)(3^j)-(2^(i+l))+(3^k), and I don't see an easy way to change that to 3^a - 2^b. It's a good try, though, thank you. No, what I think will be required is something very, very clever, because I've worked on it for quite a while and I still just don't see it. My idea is to use the fact that all linear combinations of 3 and 2 are multiples of their gcd (which is one) so we can in principle use linear combinations to get all integers... but the only coefficients to 3 we are allowing are powers of 3 and the only coefficients of 2 we use are powers of 2... so from our list of results of linear combinations, we can automatically strike out any products of 2 or 3. IOW, 3a-2b=the integers, when a and b are integers; but now I'm restricting a and b to powers of 3 and of 2, respectively. Now I just have to show that restricting our coefficients didn't eliminate any other answers than the products of 2 or 3. Any ideas?

 

[Xevarion]

If i = 1 and j=k you will have the right form. Or if the representation of the smaller number is 2^l - 3^j, you have 2^{l+i} - 2^i3^j + 3^k so if i = 2 and j+1 = k or i = 1 and j=k still works too.

So what I was suggesting was trying to figure out if one of those three cases must happen if you do it for all values of k.

Compare Putnam 2005 A1: http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/2005.pdf"
(http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/2005s.pdf" )

Another option (which I didn't think about so I don't know if it has any potential) would be to allow a or b to also take values which are 0 or powers of the other number, so that you can make any integer again. Then try an inductive proof of that statement.

By the way, do you know if this is actually true? Or is it your conjecture? Let's look for patterns:
3-2=1
9-4=5
9-2=7
27-16=11
16-3=13
81-64=17
27-8=19
27-4=23
27-2=25
32-3=29
I can't figure out how to do 31. I'm having trouble with some of the ones after it too, actually.

 

[D H]

I can't figure out how to do 31. I'm having trouble with some of the ones after it too, actually.

$$31=2^5-3^0$$

 

[rs1n]

$$31=2^5-3^0$$

Hehe, this reminds me of a story (possibly just rumor) of a grad student who was asked to factor the number 6 in $$Q(\sqrt{-5})$$ two different ways during a prelim. The idea was to start with very simple questions to get the student to be less nervous. The student was able to get:

$$6 = (1+\sqrt{-5})(1-\sqrt{-5})$$

but was unable to find a second factorization. The story is probably just rumor, but I can imagine someone being nervous enough to overlook $$6 = 2\cdot 3$$

 

[Xevarion]

Sorry, I didn't realize we were allowing 0th powers too. (It seems to go against the OP's idea about generalization of GCD -- raising to a 0th power is like multiplying by 0 in $am + bn = c$. Then also we can obtain lots of multiples of 2 or 3: 3-1 = 2, 9-1 = 8, 4-1 = 3...)

Even then, I don't think I can do 35 with reasonably small powers either, and that isn't trivialized by adding in 0th powers.

 

[approx]

well, we can fix the problem with 31 and 35 if we allow addition,
27+4
27+8
and thanks for the link and idea, I've only got a minute, but I'll check it out a little later.

 

[Xevarion]

I didn't say it's not possible to do 31 and 35 with subtraction only -- I'd be interested to see if powers of 2 and 3 continue to be close together sometimes even when the powers are high. For example, 13 = 16-3 but also 13 = 256 - 243. But up to the next several powers of 3 that I know, there aren't any that are very close to powers of 2.

Here's a slightly more general version. Let $A = \{2^n3^m : n, m \in \mathbb{N}\}$. What is $A + A = \{a_1 + a_2 : a_1, a_2 \in A\}$? What about $A-A$? Here's a 'philosophical' reason for why we would expect those two sets to be big: by definition it's clear that $A * A = A$. There's a general idea in the field of arithmetic combinatorics that if $A*A$ is not much bigger than $A$, then $A + A$ must be big. You can see this, for example, in Lagrange's four squares theorem. The set $S$ of perfect squares is also closed under multiplication, and $S + S + S + S \supset \mathbb{N}$ (if you include 0). But our set $A$ is much less dense than the set of squares...

edit: sorry, I forgot that this forum uses tex-tags instead of $. I am kinda too lazy to go replace them all...

 

[approx]

clarify

So let me see if I get this...

...Huh?


BTW, using plus or minus was part of the original conjecture, but I am curious whether plus is needed.

 

[CRGreathouse]

Here's the part where I pop in with some numerical evidence.

I have trouble with 53, 71, and 95. If the conjecture holds for these numbers, then the constituent powers are at least 10^100,000. The other numbers = 1 and 5 mod 6 below 100 work.

I found several dozen examples below 500, but have verified them to only to 10^20,000.

 

[CRGreathouse]

My opinion, notwithstanding Xevarion's enlightened post, is that this is an example of Guy's strong law of small numbers. I don't think there are enough powers of 2 and 3 for this to work.

Wait, that's an idea for a proof. There are more than n/3-2 numbers which are 1 or 5 mod 6 up to n, and less than (1 + log_2 n)(1 + log_3 n) pairs of powers of 2 and 3, respectively. Each pair may produce at most two distinct values, adding and subtracting. (There are three possibilities, a-b, b-a, and a+b, but one is nonpositive.) This sets a lower bound on the value of at least one set member. (1 + log_2 n)(1 + log_3 n) is bounded above by (log_2 n)^2 for n >= 32.

Let's see... there are 2n numbers in the right residue classes up to 6n, so at least one of those must be greater than 2^√2n. That at least shows how far you'd need to check. Using tighter bounds, to check up to 1000 at least one power must exceed 4,500,000; to check up to 5000 at least one power must exceed 1,000,000,000,000,000.

Hmm, that's less impressive than I'd hoped.

 

[rs1n]

I haven't given this problem much though, but my initial reaction was:

What about writing a number m (not divisible by 2 or 3) as an expansion of powers of 2, and then powers of 3?

Every integer can be written as the sum of powers of 2, with coefficients being either 0 or 1; similarly, every integer can be written as the sum of powers of 3, with coefficients in {-1, 0, 1}.

 

[Xevarion]

OK I think I have an idea for how to disprove this conjecture now. It could get a bit technical, though.

CRGreathouse basically said that one must go to very large powers of 2 and 3 in order to make all of the numbers in a certain (relatively small) interval. We'd like to show that going to very large powers 'won't help'. So, let's consider the situation mod $$p$$, where $$p$$ is a very large prime number. Define $$A = \{2^m \pmod p | m \in \mathbb{N}\} \cup \{3^m \pmod p| m \in \mathbb{N}\}$$. The objective would be to show that $$A-A$$ or $$A+A$$ or at least $$A + (A \cup -A)$$ (in the notation of my post above) is big (by which I mean $$cp$$ where $$c$$ is an absolute constant). But I don't think this can possibly be true every time...

Basically all we need to show is that there exists some $$p$$ for which $$|A|$$ is not big, because $$|A+A| \le |A|^2$$. In other words, we want that neither 2 nor 3 is a generator of the multiplicative group $$(\mathbb{Z}/p\mathbb{Z})^\times$$. Someone with a bit more NT knowledge want to help out here?

I still think it may be possible for my arithmetic combinatorics techniques to apply here. My roommate wants me to go to lunch though so it'll have to wait for a bit... :P

 

[Xevarion]

OK so it looks profitable to consider things mod 73. I found that
$$A = \{1,2,4,8,16,32,64,55,37\}, B = \{1, 3, 9, 27, 8, 24, 72, 70, 64, 46, 65, 49\}$$
so $$A + B$$ is missing $$\{14, 20, 21, 22, 27, 30, 39, 42, 44, 49, 60, 70\}$$ and $$(A-B) \cup (B-A)$$ is missing $$\{22, 51\}$$. Thus $$(A - B) \cup (B-A) \cup (A + B)$$ is missing 22, so it's impossible to make a number which is equivalent to 22 mod 73 as $$\epsilon_1 2^m + \epsilon_2 3^n, \epsilon_i = \pm 1$$. The first example which is relevant (ie not divisible by 2 or 3) is of course 95.

This agrees with CRGreathouse's numerical evidence (i.e. 95 was one of the ones that didn't have any solution with numbers less than $$10^{10^5}$$).

 

[Xevarion]

Some remarks:

1) My observation about 'the general idea of arithmetic combinatorics' is not relevant in this case, because although $$A\cdot A = A$$ and $$B \cdot B = B$$, $$A \cdot B$$ is probably big so there's no reason to expect too much from $$A + B$$ or $$A-B$$.

2) It's still possible to salvage the OP's idea in a couple of different ways.

(i) One would be to ask what proportion of (1 and 5 mod 6) numbers can be made via the desired operation. I've shown that it's at most $$\frac{72}{73}$$ but I would guess it's actually much less than that. (I wouldn't even be surprised if the density of numbers which can be made in that way is $$o(N)$$.)

(ii) Alternatively, one could try to use the idea I suggested (re: (1)) and see what happens if you add/subtract numbers of the form $$2^i3^j$$. The Putnam problem I referred to earlier shows that even if you add an additional restriction on what sort of sums you're allowed to take, you can still get every number as a sum of some number of $$2^j3^j$$ (but the number required may be big, like to get all numbers up to $$N$$ you might need to do sums of about $$\log(N)$$ terms). Without the restriction from the Putnam problem, does the number of required terms go down? What's the optimal bound? Alternatively, what's the density of the set of numbers you can get by doing sums of just $$k$$ such terms?


ps -- sorry for the triple post. hopefully the fact that the posts all have actual useful content will redeem me? ;-)

 

[D H]

I found that
$$A = \{1,2,4,8,16,32,64,55,37\}, B = \{1, 3, 9, 27, 8, 24, 72, 70, 64, 46, 65, 49\}$$
so ... $$(A-B) \cup (B-A)$$ is missing $$\{22, 51\}$$.

Since 2 is in A and 24 is in B, then (2-24)%73=51 is in A-B and 24-2=22 is in B-A. Those missing elements aren't missing.

 

[CRGreathouse]

Bravo, Xevarion! Excellent show, not too technical at all. I'm curious to see if anyone has a way to move forward on your suggestions for salvaging the conjecture, though I also suspect that the sequence is of density zero.

hopefully the fact that the posts all have actual useful content will redeem me? ;-)

Absolutely.

 

[Xevarion]

Oops! DH is right! Let me go back and check those... maybe a prime greater than 73 will be necessary...

 

[D H]

Xevarion's technique seems to work with 683. The "missing" numbers modulo 683 are {20, 32, 34, 46, 58, 70, 86, 87, 93, 117, 124, 133, 138, 147, 150, 151, 153, 157, 159, 160, 163, 166, 167, 171, 173, 178, 181, 182, 190, 206, 207, 213, 214, 215, 216, 223, 250, 278, 287, 298, 299, 306, 322, 330, 353, 361, 377, 384, 385, 396, 405, 433, 460, 467, 468, 469, 470, 476, 477, 493, 501, 502, 505, 510, 512, 516, 517, 520, 523, 524, 526, 530, 532, 533, 536, 545, 550, 559, 566, 590, 596, 597, 613, 625, 637, 649, 651, 663}. 133 is the first that is neither a multiple of 2 or 3.

Edit:

Now it might be my turn to be speaking too soon. My little perl script coughed up something completely different for 1093 and 1181.

 

[D H]

My turn for multiple posts. Trying to fully grok Xevarion's technique.

Now, 133 mod 73 is 60. If I understand Xevarion's technique correctly, just because 60 is not in the (empty) "not represented" list for 73 does not mean that a solution exists for 133. It just means a solution might exist. On the other hand, because 133 and 151 and ... are in the "not represented" list for 683 means that there is no solution of the desired form for 133 (or 151, or ...). So that fact that 133 (or 151, or ...) do not turn up in the "not represented" lists for 1093 and 1181 does not mean that a solution exists for 133.

 

[approx]

The Real Conjecture

Thanks so much for all the help, I haven't time to read it all right now, but I'll look it over as soon as possible. It looks promising. Meanwhile, I have a more general conjecture which might avoid some of the problems of not having enough low exponents to account for all primes, by giving us more equations to work with. As it is a separate conjecture, I am going to put it into its own thread. See what you think.
approx

 

[Xevarion]

Right. I also realized that it's not necessary for the number we mod by to be prime (and in fact it's better if it's not). So, consider mod 91. We have
$$A = \{1, 2, 4, 8, 16, 23, 32, 37, 46, 57, 64, 74\}$$
$$B = \{1, 3, 9, 27, 61, 81\}$$
So $$(A - B) \cup (B - A)$$ is missing $$\{6, 9, 16, 21, 27, 39, 40, 41, 50, 51, 52, 64, 70, 75, 82, 85\}$$. It's possible I have arithmetic errors again and some of this isn't right, but there are so many that I can't believe all of them are wrong...
And $$A + B$$ is missing a lot, I got $$\{1, 8, 12, 14, 15, 18, 20, 21, 23, 30, 37, 39, 42, 45, 48, 51, 52, 53, 56, 57, 61, 68, 70, 71, 72, 74, 76, 78, 79, 80, 81, 86, 87, 88, 90\}$$.

In all, it appears we can never make any number equivalent to 21, 39, 51, 52, or 70 mod 91 by adding or subtracting powers of 2 and 3. So the smallest number (1 or 5 mod 6) that we can't make (according to this computation, not the smallest possible overall) is 143.

Anyone who can program (DH?) want to check my work for me? I did this all by hand...

 

[CRGreathouse]

Xevarion's technique seems to work with 683.

Funny, I was just about to post the same thing.

And yes, composites do seem to work better -- I'll check that one, Xev.

 

[Xevarion]

Just for other readers -- the reason that composites work better is that the order of 2 and 3 tends to be smaller mod a composite. Basically, we want there to be very few possible residues for $$2^m$$ and $$3^m$$ mod N. The way I picked 91 was by going to the list of integer sequences and finding the lists for the multiplicative order of 2 mod N and the same for 3. Then I went along the two lists until I found an N where both numbers were small (in this case, 6 and 12). We know that we can't make much stuff if $$|A| = 12$$ and $$|B| = 6$$, because as I said before $$|A + B| \le |A||B|$$ (and similarly A-B and B-A). So A+B can't possibly hit everything -- even if there's no duplication, we can only make 72 different residues mod 91 by adding a power of 2 to a power of 3. For differences, we had to hope that there was a lot of overlap, but we'd expect the set of powers of 2 and 3 to be essentially random and independent mod a large number (from the perspective of how often you get repeated differences). In modern jargon, the additive energy of A and -B is about what you'd expect for random subsets of $$\mathbb{Z}/91\mathbb{Z}$$.

 

[D H]

Anyone who can program (DH?) want to check my work for me? I did this all by hand...

Ouch. By hand? You did fine this time.

I realized you could even look at multiples of 2 (or 3) as moduli (spelling?). In case of multiples of 2 (or 3), multiples of 2 (or 3) have to be removed from the complement of $(A - B) \cup (B-A) \cup (A + B)$ because we don't care about these values. With that, the non-multiples of 2 or 3 less than 100 that are in the complement of the reachable numbers modulo some integer p<=999 (or p<=133, for that matter) are 53, 71, and 95.

Here's the part where I pop in with some numerical evidence.

I have trouble with 53, 71, and 95. If the conjecture holds for these numbers, then the constituent powers are at least 10^100,000. The other numbers = 1 and 5 mod 6 below 100 work.