Wikipedia:Reference desk/Archives/Mathematics/2016 July 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 30

How many different color images could there be?

Assume we had an image of the size 1024x768 pixels (the size of some monitors) and we were using .jpg format. How many unique images could be created within those constraints? I know this depends on the number of possible colors in a .jpg. I'm assuming (possibly incorrectly) there are old school jpegs with a smaller number of colors and newfangled jpegs with a huge number of colors. Just pick a number of possible colors that is relatively common, including black and white, of course. Anyway, I'm assuming the number of possible images is very large but finite. I was hoping you could display the answer in exponential format (no factorials or anything else). if it's a crazy big number like googolplex you could express it (10^10)^10, I think [edit: I now think that expression for googolplex is probably wrong. sorry!].

Also, one last part to my question. What if the image was pure black and white only (no grayscale). How many images could you make? Just curious. Thanks, --Captain Breakfast (talk) 11:51, 30 July 2016 (UTC)

JPEG uses lossy compression (except for rarely used Lossless JPEG) so it's unclear how many images can be represented or which image is actually represented by a given JPEG file. This is the mathematics desk and not computing so let's instead assume a bitmap format like PNG or GIF where every potential image can be represented. 1024×768 = 786432. If each pixel can have n colors then there are n⁷⁸⁶⁴³² possible images. If a color is represented with m bits and all 2^m combinations are valid colors then it becomes (2^m)⁷⁸⁶⁴³² = 2^786432m. You can compute it as a power of 10 by multiplying the exponent by log(2)/log(10), around 0.30103. For 32-bit colors it becomes 2^25165824, around 10^7575668. For 2 colors it becomes 2⁷⁸⁶⁴³², around 10²³⁶⁷⁴⁰. In both cases the number of decimal digits is given by the power of 10. PrimeHunter (talk) 12:14, 30 July 2016 (UTC)

You might be interested in The Library of Babel, or perhaps the images at [1] which at least have some meaning behind them - I think. So how would one count 'meaningful' pictures? Dmcq (talk) 17:16, 30 July 2016 (UTC)

Viewers accept Lossy compression of digital images because they do not notice substitution for a correct image of a numerically different image, thus the number of perceptually unique images is less than the number of quantitatively unique images. PrimeHunter calculates the latter. The result numbers in exponential format are astronomically large and exceed the number of images a person can consciously distinguish in a lifetime. (Note that the GIF format mentioned is limited in practice to m = 8-bit indexed colours.) The answer to the number of perceptually unique images that might be shown on a monitor depends on the viewer's discrimination which varies with person and viewing situation. We may assume that the JPG format is traditionally applied to continuous-tone images such as landscapes or portraits that are viewed as a whole, without considering subjects such as line drawings where the eye may focus on a local detail of a few pixels. Some standardized testing procedures have been developed for subjective video quality testing that could be the basis for establishing uniqueness threshold statistics. That would require extensive viewing tests where random sized groups of pixels are changed by random amounts many times and a database is collected to discover the average change (in brightness and colour) that makes an average viewer conscious that an image has been replaced by another, i.e. that makes her aware of 2 unique images.

A googolplex is the number 10^googol, or equivalently, 10¹⁰¹⁰⁰. AllBestFaith (talk) 14:11, 31 July 2016 (UTC)

Halting problem

Some contributors to this desk might be interested in looking at this question on the Computing Desk. --69.159.9.219 (talk) 16:26, 30 July 2016 (UTC)

Number of Solutions

Is that true that the number of real solutions of an equation of the form $\sum _{i=1}^{n}{a_{i}\cdot x_{i}^{\frac {1}{i}}}=c$, where both $\{a_{i}\}$ and $c$ are constants, is polynomial in n? 185.32.179.24 (talk) 18:13, 30 July 2016 (UTC)

• Did you not ask a similar question before? We will not do your homework; say what you tried and tested. First, write that equation in polynomial form. When that is done, try to formulate a better question (what do you mean exactly by "the number of solutions is polynomial in n"?). Tigraan^{Click here to contact me} 18:40, 30 July 2016 (UTC)

I'd asked a similar question: I'd asked how to find its solutions, and I was told to convert it into a polynomial. Now, I am seeking for a bound on the number of roots of that polynomial (there is, of course, a trivial bound: the degree of the polynomial - which is exponential in n - but I guess that there's some better bound). So far, I am really stuck, so I tried to investigate special cases. In such cases I noticed that there's one real solution or not at all, but I guess it's not the case in general. 18:57, 30 July 2016 (UTC) — Preceding unsigned comment added by 185.32.179.24 (talk)

Just to clarify a couple things: First I think you meant to write x instead of x_i, otherwise you have more unknowns than equations and the number of solutions would be infinite. Second, I'm taking polynomial to mean polynomial order, i.e. the number of solutions is bounded by a polynomial in n. This is common abuse of language but it might not be clear from the context. I'd also like to note that when you convert the equation to a polynomial you get one of degree M(n) where M(n) is the l.c.m. of the integers from 1 to n (OEIS: A003418). I don't know what the rate of growth of this function is but it's apparently not polynomial. Finally, it's not hard to construct an example with more than one solution; one is 3x^1/2-x=2 which has solutions x=1,4. --RDBury (talk) 21:59, 30 July 2016 (UTC)

After you convert to a polynomial equation, there are exactly (n+1) terms including the constant. By Descartes' rule of signs, the number of real, positive and negative, roots cannot be more than n. Loraof (talk) 22:07, 30 July 2016 (UTC)

Good catch, but I don't think the reasoning is quite right. For example x⁴-5x²+4 has only three terms but it has 4 real zeros. But you do get that the number of solutions is at most 2n which is polynomial in n. Btw, an example with 3 roots is 1729x^1/3-840x^1/2+11x=900. Basically take any n positive numbers, then take these to be solutions to get a system of linear equations for the coefficients. Now solve to get an example with n roots. --RDBury (talk) 22:25, 30 July 2016 (UTC)

In your first example, there are two sign changes, and two positive real roots. The second example does not appear to have any. It seems (to me at least) that Loraof's link allows the bound to be reduced from n if the signs of the coefficients are known. —Quondum 01:59, 31 July 2016 (UTC)

The first example was to show that the number real zeros can be larger than the number of non-zero terms (including the constant). Descartes tells you is that the number of zeros must be less than twice the number of terms. In the second example the rhs should be 900, not 0. In that case Alpha does find the three roots, 1, 64 and 729. --RDBury (talk) 09:31, 31 July 2016 (UTC)

Sorry, my bad. Though using care to apply the logic carefully (bringing the constant to the left, constraining to positive x and using the principal roots), it remains a fruitful result. —Quondum 14:09, 31 July 2016 (UTC)

Thank you for your answers! I was really stuck on it for several days! 185.32.179.35 (talk) 06:45, 31 July 2016 (UTC)

Just a caveat: you have not specified needed constraints on the problem. In particular, if we allow each term to be a multivalued function on the complex numbers, things get nasty. The neat bound applies only if you restrict all values to real numbers, x positive, and the (1/i)th power to the principal ith root. —Quondum 14:09, 31 July 2016 (UTC)

Thank you for the caveat! I assume all of these assumptions except for the assumption that x is positive. Why does it get nasty without this assumption? 185.32.179.35 (talk) 15:15, 31 July 2016 (UTC)

Elaborating on Quondum's point: The transformation to a polynomial equation is $x=y^{L}$ where L is the least common multiple of the exponents' denominators. Now there are at most 2n real solutions, and some non-real solutions, for y. But some of those non-real solutions for y may give real solutions for $x=y^{L}.$

Incidentally, when I wrongly stated the upper bound is n rather than 2n, I believe that would have been right if the exponents in the polynomial equation strictly alternate between even and odd. Loraof (talk) 15:31, 31 July 2016 (UTC)

More concretely, (ignoring the case of n = 0, where if c = 0 we have an infinite number of roots), with the stated assumptions other than x > 0, if there is at least one nonzero a_i for an even i, then the expression is not defined for negative x. Hence for this case we have an upper bound of n roots. If all the a_i for even i are zero, we can say that the maximum number of positive roots is n, and separately for the bound on the negative roots, leading to a simplistic bound of 2n + 1 (allowing for a root at zero). However, in this the case of odd i only, we have approximately halved the number of positive roots, as well as the number of negative roots, so we still have an absolute bound very close to n counting all roots, which I'm pretty sure is n using a heuristic argument (the proof of the exact value should not be difficult). —Quondum 16:33, 31 July 2016 (UTC)

On the question about nastiness: I was not referring to the assumption x > 0 (which we now seem to be able to drop), but to multi-valuedness. —Quondum 18:55, 31 July 2016 (UTC)

I'd misundertood you before. Thank you! עברית (talk) 18:04, 1 August 2016 (UTC)

The OP may also be interested in Fermat's Last Theorem#Reciprocal integers (inverse Fermat equation) and Fermat's Last Theorem#Rational exponents. Loraof (talk) 20:25, 31 July 2016 (UTC)

Thanks for the links! They're really interesting! עברית (talk) 18:04, 1 August 2016 (UTC)