Proving Invariance of Polynomial Size Measurement for Positive n

[msmith12]

For a positive natural number n, we use
$$|n|= \log_{2}n$$
as the measure of the size of n (which is the number of bits in n's binary representation). however, in most cases the size of n can be written as log n without giving an explicit base (the omitting case is the natural base e). Show that for any base b>1,
$$\log_{b}n$$
provides a correct size measure for n, i.e., the statement "a polynomial in the size of n" remains invariant for any base b>1.


This was a problem in my homework for cryptography...

I understand the first part of the problem, which basically means that for any base, b:

$$\log_{b}n=|k| => b^{[k]+1} > n$$
where [k] equals the floor of k.

but beyond that, I really have no idea...

thanks for any help

matt

 

[member 553083]

hewThe statement "a polynomial in the size of n" is referring to a polynomial that depends on the size of n, i.e., a polynomial of the form p(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n, where x represents the size of n. To show that this polynomial remains invariant for any base b>1, we must show that the coefficients of the polynomial do not change when changing the base. Let's consider an example polynomial, p(x) = a_0 + a_1 x + a_2 x^2. We can write this polynomial in terms of the logarithm in any base b>1 as follows:p(x) = a_0 + a_1 \log_{b}x + a_2 (\log_{b}x)^2Now, it is clear that the coefficients of the polynomial remain the same regardless of the choice of the base b, therefore showing that the polynomial remains invariant for any base b>1.

 

[wais]

To prove the invariance of polynomial size measurement for positive n, we need to show that for any base b>1, the statement "a polynomial in the size of n" remains invariant. In other words, no matter what base we use to measure the size of n, the resulting value will still be a polynomial in the size of n.

To start, let's define the size of n in terms of base b:

\log_{b}n = k

where k is the number of digits in the base b representation of n. Now, let's consider the size of n in terms of the natural base e:

\log_{e}n = m

where m is the number of digits in the base e representation of n.

We can then use the change of base formula to relate these two sizes:

\log_{b}n = \frac{\log_{e}n}{\log_{e}b}

Since b>1, we know that \log_{e}b>0. This means that \frac{1}{\log_{e}b}>0. Therefore, we can rewrite the above equation as:

\log_{b}n = m \cdot \frac{1}{\log_{e}b}

Now, let's consider the statement "a polynomial in the size of n". This means that for some polynomial function f, the size of n can be written as:

\log_{b}n = f(m)

where m is the number of digits in the base e representation of n.

We can rewrite this statement as:

m = g(\log_{b}n)

where g is the inverse function of f.

Now, let's substitute our expression for \log_{b}n into this equation:

m = g(m \cdot \frac{1}{\log_{e}b})

Notice that this is still a polynomial function of m. Therefore, we have shown that for any base b>1, the statement "a polynomial in the size of n" remains invariant. This proves the invariance of polynomial size measurement for positive n.