# Proof of maximum value?

• September 7th 2012, 05:15 PM
SlipEternal
Proof of maximum value?
So, I have been working on a problem for a while. I am trying to see what sort of maximum and minimum values it can attain. I have for a while conjectured that it attains a maximum value of $\left(\frac{4}{3}\right)^{n+1}$. I want to see if my proof follows. If anyone is willing to take a look, I would be most appreciative.

Define $A_n = \left\{2^{a_n}(2^{a_{n-1}}(\cdots(2^{a_1}(4^{a_0}-1)-3)-\cdots)-3^{n-1})-3^n\in 3^{n+1}\mathbb{Z}>0\mid a_i \in \mathbb{N}\right\}$ (Note: the $a_i$'s are all positive integers, but for not all positive integers produce elements of $3^{n+1}\mathbb{Z}$, so it doesn't span all positive integers).

Claim: $\displaymode \frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\le \left(\frac{4}{3}\right)^{n+1}$ where the denominator is an element of $A_n$.

Proof by induction on $n$.

For $n=0$, this is simply $\frac{2^{a_0}}{2^{a_0}-1}$. Since $2^{a_0}-1\in 3\mathbb{Z}$, it must be that $a_0\equiv 0 (\text{mod } 2)$, so $\frac{4^{a_0}}{4^{a_0}-1}\le \frac{4^1}{4^1-1} = \frac{4}{3}$. Assume the claim is true for all sets up to $A_{n-1}$. Then, if

$\displaymode \frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\le k$, then
$\displaymode \log_2{\left(\frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\right)\le \log_2(k)$
$\displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{(2^{a_n}(\cdots)-3^n)}\le \log_2(k)$
$\displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{2^{a_n}(\cdots)}+\log_2{2^{a_n}(\cdots)}-\log_2{(2^{a_n}(\cdots)-3^n)}\le \log_2(k)$
$\displaymode \log_2{\frac{\prod_{i=0}^{n-1} 2^{a_i}}{(2^{a_{n-1}}(\cdots)-3^{n-1})}}+\log_2{\frac{2^{a_n}(\cdots)}{2^{a_n}(\cdots )-3^n}\le \log_2(k)$

We can apply the induction hypothesis to the first term, and for the second term, we know that the bottom is an element of $A_n$ with a minimum value of $3^{n+1}$ (since every element of $A_n$ is an element of $3^{n+1}\mathbb{Z}$. And the top is then $3^{n+1}+3^n$. So, evaluating this, we get:

$\displaymode \log_2{\frac{\prod_{i=0}^{n-1} 2^{a_i}}{2^{a_{n-1}}(\cdots)-3^{n-1}}}+\log_2{\frac{2^{a_n}(\cdots)}{2^{a_n}(\cdots)-3^n}\le \log_2{\left(\frac{4}{3}\right)^n}+\log_2{\frac{3^ n(3+1)}{3^{n+1}}}=\log_2{\left(\frac{4}{3}\right)^ {n+1}$. Eliminating the logs from both sides (2 to the power of each side) yields the inequality desired, and hence by induction, proves the claim.

Is this proof correct? Am I overlooking something?
• September 7th 2012, 06:52 PM
Vlasev
Re: Proof of maximum value?
It looks good to me. What you've proven is that it must be less than or equal to this bound. Is there an element that attains this bound?
• September 7th 2012, 07:27 PM
SlipEternal
Re: Proof of maximum value?
Yes, it turns out that the minimum element is always in the set. So, for all $n$, $3^{n+1}\in A_n$. And it is simple to check that $4^{a_n}(4^{a_{n-1}}(...(4^{a_0}-1)-...)-3^{n-1})-3^n=3^{n+1}$ when $a_0=a_1=...=a_n=1$.

Edit:

I forgot to mention that the minimum element always attains the maximum bound for that ratio since:
$\frac{4^{a_n=1}\cdots 4^{a_0=1}}{3^{n+1}}=\frac{4^{n+1}}{3^{n+1}}$
• September 7th 2012, 10:44 PM
Vlasev
Re: Proof of maximum value?
Good! What is this problem related to, if I may ask?
• September 8th 2012, 11:13 AM
SlipEternal
Re: Proof of maximum value?
Let $I=\{2n-1\mid n\in\mathbb{N}\}$ be the set of odd positive integers. Define $f:I\to I$ by $f(n)=\frac{3n+1}{2^a}$ where $a$ is the largest power of 2 that divides $3n+1$. The function $f$ is sometimes called the Syracuse function, and is one of the methods used to investigate the 3n+1 Conjecture (also known as the Syracuse problem, the Collatz Conjecture, etc.).

Let $B_n = \{\frac{k}{3^{n+1}}\mid k\in A_n\}$. Notice that $f^{-(n+1)}(1) \subseteq B_n$. Now, if we want to check the asymptotic density of $f^{-(n+1)}(1)$ in $I$, we need to figure out how many elements of $f^{-(n+1)}(1)$ are less than $2m-1$ for some $m$. So, we have:

$\displaymode \frac{2^{a_n}(\cdots)-3^n}{3^{n+1}} \le 2m-1$
$\displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{\prod_{i=0}^n 2^{a_i}}+\log_2{(2^{a_n}(\cdots)-3^n)} \le \log_2(3^{n+1}(2m-1))$
$\displaymode \sum_{i=0}^n{a_i} - \log_2{\frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}} \le \frac{n+1}{\log_3{2}} + \log_2(2m-1)$

I now know that the second term on the left is bounded below by 0 and bounded above by $\log_2{\frac{4^{n+1}}{3^{n+1}}}$.
• September 8th 2012, 11:42 AM
Vlasev
Re: Proof of maximum value?
I knew it! I had a feeling it had something to do with the Collatz problem. All these 3's and 2's...
• September 8th 2012, 12:02 PM
SlipEternal
Re: Proof of maximum value?
I work on it whenever I get frustrated with my coursework. I find it relaxing to work on a problem that I don't care if I make any progress on. It helps relieve stress from grad school.