Wikipedia:Reference desk/Archives/Mathematics/2010 December 5

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.

December 5

Quadratic Residues

Suppose we're working in $\mathbf {F} _{p}$ (p an odd prime), and we have $n\in \mathbf {F} _{p}$ a quadratic residue. Cipolla's algorithm claims that there are $(p-1)/2$ different $a\in \mathbf {F} _{p}$ such that $a^{2}-n$ is not a square. Why is this?

To put this another way, for $y$ a random element of $\mathbf {F} _{p}$, there's a (roughly) 50% chance that $y$ is a quadratic residue, and a roughly 50% chance that $y-n$ is. Why are these independent?--203.97.79.114 (talk) 07:25, 5 December 2010 (UTC)

I suppose n ≠ 0, otherwise it's obviously not true. First, if n = b², then a² − n is a square if and only if (a/b)² − 1 is a square, hence there is a single number k such that for every nonzero square n, there are k elements a such that a² − n is a square. 2 of these elements give a² − n = 0, which has a unique square root, and for each of the remaining k − 2 there are 2 square roots. On the other hand, if n = 0, then a² − n is always a square, and it has one or two square roots depending on whether a = 0. If we sum all this together, we see that $|\{(a,b,c)\mid a^{2}=b^{2}+c^{2}\}|=|\{(a,b,c)\mid a^{2}-b^{2}=c^{2}\}|=1+2(p-1)+(p-1)2+2(p-1)(k-2)=2k(p-1)+1$. Now, let's count the set $\{(a,b,c)\mid a^{2}=b^{2}+c^{2}\}$ in a different way. Using Fibonacci's identity

$(x^{2}+y^{2})(u^{2}+v^{2})=(xu-yv)^{2}+(xv+yu)^{2}$

we see that the set $\Box +\Box =\{x\mid \exists b,c\,(x=b^{2}+c^{2})\}$ is closed under multiplication, hence $G=(\Box +\Box )\setminus \{0\}$ is a subgroup of $\mathbf {F} _{p}^{\times }$. It contains the subgroup of squares, and it contains it properly (otherwise the set of squares is closed under addition of 1, which implies by induction that every element is a square, which is not true). But the subgroup of squares has index 2, hence $G=\mathbf {F} _{p}^{\times }$, i.e., every element is a sum of two squares. Moreover, using Fibonacci's identity again, we see that the number of representations of any nonzero element as the sum of two squares is the same, let's call this number s. Also let s₀ be the number of representations of 0 as the sum of two squares (which is 1 or 1 + 2(p − 1), depending on whether −1 is a square). Then $p^{2}=|\{(x,b,c)\mid x=b^{2}+c^{2}\}|=s_{0}+(p-1)s$. Since the square of a nonzero element is nonzero, the same argument gives $|\{(a,b,c)\mid a^{2}=b^{2}+c^{2}\}|=s_{0}+(p-1)s$, hence $|\{(a,b,c)\mid a^{2}=b^{2}+c^{2}\}|=p^{2}$, thus $k={\frac {p^{2}-1}{2(p-1)}}={\frac {p+1}{2}}$. Consequently, the number of a such that a² − n is not a square is p − (p + 1)/2 = (p − 1)/2. I have a feeling that this whole argument is more complicated than necessary, maybe I'm just missing something simple.—Emil J. 18:14, 6 December 2010 (UTC)

Trouble with finding Arc length

I'm in a calculus I class and I am attempting to find the Arc length of 4/5x^5/4 on [0,4]. I know I must differentiate 4/5x^5/4 and square it; this yields x^1/2 if I'm correct. from this point I need to integrate the square root of (1 + x^1/2). this is where I am having trouble: Should I use U-substitution (U = 1 + x^1/2)? If so, what is my du = dx going to be? Thanks for the help.161.165.196.84 (talk) 12:01, 5 December 2010 (UTC)

The easiest way to do substitutions is to treat the Leibniz notation for the derivative, ${\frac {du}{dx}}$, as literally dividing du by dx. Then you have $dx=du/\left({\frac {du}{dx}}\right)$, and you should express x in terms of u to get a result in all u's. You should spend some time understanding why this works.

Anyway, using $u=1+{\sqrt {x}}$ will move you forward but I think you'll then need another substitution to complete the solution. I'd go with $u={\sqrt {1+{\sqrt {x}}}}$ which leaves you with an integral you can look up in a table, or else solve with a very simple partial fraction decomposition. -- Meni Rosenfeld (talk) 12:16, 5 December 2010 (UTC)

Alternatively, the substitution u² = 1 + √x, which by implicit differentiation yields

${\frac {du}{dx}}={\frac {1}{4u(u^{2}-1)}},$

gives you an easy integral and a quick solution. —Anonymous Dissident^Talk 07:47, 6 December 2010 (UTC)

how do you calculate the probability of something that has never happened?

how do scientists calculate the probability of something that has never happened? Thanks. 80.14.38.186 (talk) 12:51, 5 December 2010 (UTC)

If it's something which works according to well-understood principles, you can reason about it with a simple application of Probability theory. If the principles themselves are subject to uncertainty, you may have to use the Bayesian interpretation of probability. -- Meni Rosenfeld (talk) 13:14, 5 December 2010 (UTC)

Sometimes it's easy. Say the odds of winning the lottery are 1 in 1 000 000. Then we can calculate the odds of winning twice in a row (even if it's never happened) to be 1 in (1 000 000)². The theorems and formulas used to mathematically calculate probabilities have nothing to do with whether things have happened. I imagine you're thinking of much more complicated scenarios, but they'll use similar tricks: compute or observe lots of data about known probabilities (of things that have happened), and then multiply and add them together in various ways. Staecker (talk) 13:20, 5 December 2010 (UTC)

See also Rule of three (medicine), which perhaps would be better titled rule of three (statistics) ? --Qwfp (talk) 14:22, 5 December 2010 (UTC)

See the Drake Equation for an example of how to calculate the probability of something complex that may, or may not, exist: intelligent life (we know it doesn't exist on Earth, but there's still some hope for the rest of the universe :-) ). StuRat (talk) 06:44, 6 December 2010 (UTC)

Medians of percentages

I'm in need of a little statistical advice here. At the top of our article Usage share of web browsers is a chart that lists the percentage results of several surveys of web browser popularity. The chart also includes, for each browser, the median percentage value from those surveys.

On the talk page, I've suggested that the median of percentages is not especially meaningful, and can be expected to distort the data. Others disagree. It seems to me that this is a matter of statistical practice, not a content dispute: in my experience, one doesn't use the median over multiple surveys like this; the median is used to show a representative central value of a population, and the percentages reported by several surveys of a population are not themselves the population. Hence my question:

Under what circumstances are the medians-of-percentages, as presented in that article, a meaningful representation of the underlying data? --FOo (talk) 15:11, 5 December 2010 (UTC)

See Median filter, http://www.drdobbs.com/article/printableArticle.jhtml;jsessionid=CHKHFCP2YYZXZQE1GHPCKHWATMY32JVN?articleId=184411079&dept_url=/ . My guess is that for your purpose, the mean is better. 92.15.31.223 (talk) 19:44, 5 December 2010 (UTC)

The mean would be better only if it were weighted according to the size of the survey. The median as used is simply the result of the middle survey, and is a simple (though probably inaccurate) proxy for the true mean if survey size is not known. Dbfirs 23:54, 5 December 2010 (UTC)

Finding the mean using the sample size of each survey makes some sense, but only accounts for one type of error, that due to a small sample size. There might also be bias in the way the question was asked, whom was asked the Q, etc. So, if we don't have any basis for comparing this type of error, perhaps it is best just to weight all surveys equally. Otherwise, a large but highly biased survey may swamp the rest. StuRat (talk) 06:40, 6 December 2010 (UTC)

The median and Bias of an estimator articles mention this issue - the median may be more robust. See Robust statistics. 92.24.184.218 (talk) 12:07, 6 December 2010 (UTC)

Solving under multiple square roots

Acknowledging the possibility of spurious roots and presuming variables to be positive for simplicity, solving ${\sqrt {x}}=y$ is trivial, and for ${\sqrt {x}}+{\sqrt {x+1}}=y$ we may square, rearrange, and square again to get $2x(x+1)=(y^{2}-2x-1)^{2}$. But if there are three or more, squaring will not in general reduce the number of terms with square roots. (I do see that $({\sqrt {a}}+{\sqrt {b}}+{\sqrt {c}})^{2}=a+b+c+2{\sqrt {ab}}+2{\sqrt {ac}}+2{\sqrt {bc}}$, so that after removing the non-radical terms and squaring again we get $4(ab+ac+bc+2a{\sqrt {bc}}+2b{\sqrt {ac}}+2c{\sqrt {ab}})$. So what's under a radical never gets any worse, but neither does it get better.) Is there any standard approach to solving such equations? --Tardis (talk) 17:44, 5 December 2010 (UTC)

Let's start with the basics. You usually want to move square roots from one side to another so there will be a roughly equal number. If you have ${\sqrt {a}}+{\sqrt {b}}+{\sqrt {c}}=d$ you first write ${\sqrt {a}}+{\sqrt {b}}=d-{\sqrt {c}}$ and then square. A trickier one is ${\sqrt {a}}+{\sqrt {b}}+{\sqrt {c}}={\sqrt {d}}+{\sqrt {e}}$ - usually it can't be simplified this way but sometimes it can, for example ${\sqrt {2x+4}}+{\sqrt {2x+2}}+{\sqrt {x-1}}={\sqrt {4x+2}}+{\sqrt {x+3}}$.

For more general methods, we had a discussion about it here. -- Meni Rosenfeld (talk) 18:13, 5 December 2010 (UTC)

It may be worth noting here that it is an open problem whether one can test $\sum _{i<n}{\sqrt {a_{i}}}\geq \sum _{j<m}{\sqrt {b_{j}}}$ in polynomial time, given integers a_i, b_j, see e.g. [1].—Emil J. 15:29, 7 December 2010 (UTC)

Integer sequence

What's the rule for this sequence? I already searched OEIS and used Mathematica's Fit function, but I didn't get anything.

0, 1, 7, 50, 404, 3756, 40180, 492576, 6883576

--70.134.49.69 (talk) 21:22, 5 December 2010 (UTC)

Can you provide any context? —Bkell (talk) 22:27, 5 December 2010 (UTC)

For what it's worth, Superseeker doesn't return anything either. —Bkell (talk) 22:32, 5 December 2010 (UTC)