# Thread: Proof of maximum value?

1. ## 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 $\displaystyle \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 $\displaystyle 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 $\displaystyle a_i$'s are all positive integers, but for not all positive integers produce elements of $\displaystyle 3^{n+1}\mathbb{Z}$, so it doesn't span all positive integers).

Claim: $\displaystyle \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 $\displaystyle A_n$.

Proof by induction on $\displaystyle n$.

For $\displaystyle n=0$, this is simply $\displaystyle \frac{2^{a_0}}{2^{a_0}-1}$. Since $\displaystyle 2^{a_0}-1\in 3\mathbb{Z}$, it must be that $\displaystyle a_0\equiv 0 (\text{mod } 2)$, so $\displaystyle \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 $\displaystyle A_{n-1}$. Then, if

$\displaystyle \displaymode \frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\le k$, then
$\displaystyle \displaymode \log_2{\left(\frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\right)\le \log_2(k)$
$\displaystyle \displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{(2^{a_n}(\cdots)-3^n)}\le \log_2(k)$
$\displaystyle \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)$
$\displaystyle \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 $\displaystyle A_n$ with a minimum value of $\displaystyle 3^{n+1}$ (since every element of $\displaystyle A_n$ is an element of $\displaystyle 3^{n+1}\mathbb{Z}$. And the top is then $\displaystyle 3^{n+1}+3^n$. So, evaluating this, we get:

$\displaystyle \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?

2. ## 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?

3. ## Re: Proof of maximum value?

Yes, it turns out that the minimum element is always in the set. So, for all $\displaystyle n$, $\displaystyle 3^{n+1}\in A_n$. And it is simple to check that $\displaystyle 4^{a_n}(4^{a_{n-1}}(...(4^{a_0}-1)-...)-3^{n-1})-3^n=3^{n+1}$ when $\displaystyle 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:
$\displaystyle \frac{4^{a_n=1}\cdots 4^{a_0=1}}{3^{n+1}}=\frac{4^{n+1}}{3^{n+1}}$

4. ## Re: Proof of maximum value?

Good! What is this problem related to, if I may ask?

5. ## Re: Proof of maximum value?

Let $\displaystyle I=\{2n-1\mid n\in\mathbb{N}\}$ be the set of odd positive integers. Define $\displaystyle f:I\to I$ by $\displaystyle f(n)=\frac{3n+1}{2^a}$ where $\displaystyle a$ is the largest power of 2 that divides $\displaystyle 3n+1$. The function $\displaystyle 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 $\displaystyle B_n = \{\frac{k}{3^{n+1}}\mid k\in A_n\}$. Notice that $\displaystyle f^{-(n+1)}(1) \subseteq B_n$. Now, if we want to check the asymptotic density of $\displaystyle f^{-(n+1)}(1)$ in $\displaystyle I$, we need to figure out how many elements of $\displaystyle f^{-(n+1)}(1)$ are less than $\displaystyle 2m-1$ for some $\displaystyle m$. So, we have:

$\displaystyle \displaymode \frac{2^{a_n}(\cdots)-3^n}{3^{n+1}} \le 2m-1$
$\displaystyle \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))$
$\displaystyle \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 $\displaystyle \log_2{\frac{4^{n+1}}{3^{n+1}}}$.

6. ## 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...

7. ## 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.