Wikipedia:Reference desk/Archives/Mathematics/2006 July 8

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

< July 7 Mathematics desk archive July 9 >

problem of two independent databases

There is a problem that teacher gave us at the university, and he claimed he has a very good solution (see below) for it, but unfortunately I was missing from the class when he explained that, so I don't know this solution, nor the name of the problem to find it on the internet (I tried).

The problem is: There are two identical databases each with n records and cannot communicate. Invent the most efficient way (in terms of number of records you need to read from databases) how to get a certain record from the database in such a way that database owners would get no information about what record did you retrieve.

The simplest way to do that is to download the whole database and look at the record you want (this will take n records to download). There is more efficient way though - if you consider records in database are ordered in the square. You can select a random subset of rows. Then ask the first database to give you the logical xor of all rows in your subset, and ask the second database also to give you the logical xor of all rows in your subset, except (or included) the row that you want. Then you can make logical xor of results and look at the correct column. The databases got no information though, because the subset is random and then the subset with/out one row is random too. So you can manage to do it in O(n^(1/2)) records retrieved.

The point is, our teacher claimed that he has solution with O(n^(1/3)). I thought about it a lot, but I really don't know and would like to know. Has anyone ever heard of this problem and could perhaps point me to this solution? Samohyl Jan 07:53, 8 July 2006 (UTC)

Is 0=2 ???

Is 0=2? Consider x=1 Now

(x-1)² = x² - 1²

Simplifying further we get

(x-1)² = (x-1)*(x+1) [as (a²)-(b²) = (a-b)*(a+b)]

If we take (x-1) to the LHS then it will cancel out with one (x-1) from the LHS thys we will get the equation

x-1 = x+1

Substituting the value of x as 1 in the above equation we get

1-1 = 1+1

hence we get 0=2

See division by zero for an explanation. Isopropyl 08:01, 8 July 2006 (UTC)

Also, your first line is incorrect. $(x-1)^{2}=x^{2}-2x+1$

which gives 1=2 for your "answer". Isopropyl 08:03, 8 July 2006 (UTC)

Well, it's true that $(x-1)^{2}=x^{2}-1^{2}$... if and only if x=1, in which case we run into the division by zero problem in the last step. Generally though, $(x-1)^{2}\neq x^{2}-1^{2}$, try some examples where x is any number but 1. -GTBacchus^(talk) 08:10, 8 July 2006 (UTC)

Thank u very much Isopropyl

When you assume x=1 then your first equation is equivalent to 0=0. Then you transform expressions on both sides, which gives the equation equivalent to 0·0=0·2. That's of course true, but stripping (x-1) from both sides means dividing by zero, which is undefined, and so illegal. By doing so you made a reasoning that

$(0\cdot 0=0\cdot 2)\implies (0=2)$

which is obviously false. --CiaPan 17:46, 13 July 2006 (UTC)

DVD won't work!

I'm trying to rip a music DVD to put it on my ipod. I'm using PQ DVD and it comes up with an error.

It says "Invalid Disc Region. This DVD-Video disc cannot by played, because it is not authored to play in the current sysytem region. The region mismatch may be fixed by changing the system region (with DVDRgn.exe)."

I can't get it even to play in anything in my pc. Could you also give recomemdations to a good *free* DVD player program.

Thanks!

~Cathy T.~

Your DVD player must be set to the correct region in order to play your movie. This is done to reduce pirating. For example, if you have a region 3 DVD then it's a DVD that will play on region 3 players. Basically, if you get a region 0 disc then it'll play in any player. Most DVD firmwares will allow you to change your region 3 times before locking your DVD player into a region.

Also, a great free DVD player (and not to mention anything else player) is VLC Player. You can find this fantastic program right here

Hope this helps -Nitrodist 5:12 AM CST, July 8, 06

Sigh; please don't propagate myths. Region codes are a bizarre invention to control distribution, not piracy. For example, if I find a copy of Jacques Tati's delightful Les Vacances de Monsieur Hulot in France, I won't be able to play it on my North American player. Or if I take my perfectly legitimate DVD of W. C. Fields' classic The Bank Dick purchased in North America I won't be able to view it with a player whose region code is for Europe. It's implausible that either of these decades-old films is of interest to pirates. This abuse of digital rights management should be illegal (and is in some places), but purse strings control politicians, and politicians control laws. --KSmrq^T 12:12, 8 July 2006 (UTC)

So... how do I change it to work in PQ DVD? (I'm so confused! I just don't understand any of this technological computer stuff... hehe)

Thanks for the DVD player sugestion! I'm going to download it now! ~Cathy T.~

Euler-Mascheroni constant approximation

The article on the Euler-Mascheroni constant provides many different formulas equivalent to the constant. Does anyone know what formula is most commonly used by computer algebra systems and other programs in computing it? Or, more accurately, which formula converges fastest with the least computational intensity? -- He Who Is^{[ Talk ]} 15:40, 8 July 2006 (UTC)

The documentation for Mathematica says it uses the algorithm in

Brent, R. P. and McMillan, E. M. "Some New Algorithms for High-Precision Computation of Euler's Constant." Math. Comput. 34, 305-312, 1980.

For those who do not have ready access to that paper, a description of their method (and others) is available online, but the cited web page uses the deprecated "font face" markup with the Symbol typeface. Here's a wikified transcription of the relevant section:

---

A better method is based on the modified Bessel functions and leads to the formula

$\gamma ={\frac {A_{n}}{B_{n}}}-\log(n)+O(e^{-4n}),\,\!$

with

$A_{n}=\sum _{k=0}^{\alpha n}\left({\frac {n^{k}}{k!}}\right)^{2}H_{k},\qquad B_{n}=\sum _{k=0}^{\alpha n}\left({\frac {n^{k}}{k!}}\right)^{2},\,\!$

where α = 3.5911… satisfies α(log(α)−1) = 1.

This technique is quite easy, fast and it has a great advantage compared to exponential integral techniques : to obtain d decimal places of γ, the intermediate computations can be done with d decimal places.

A refinement can be obtained from an asymptotic series of the error term. It consists in computing

$C_{n}={\frac {1}{4n}}\sum _{k=0}^{2n}{\frac {[(2k)!]^{3}}{(k!)^{4}(16n)^{2k}}}.\,\!$

Brent and McMillan suggest that

$\gamma ={\frac {A_{n}}{B_{n}}}-{\frac {C_{n}}{B_{n}^{2}}}-\log(n)+O(e^{-8n}).\,\!$

This time, the summations in A_n and B_n should go up to βn where β = 4.970625759… satisfies β(log(β)−1) = 3. The error O(e⁻⁸ⁿ) followed an empirical evidence but the result had not been proved by Brent and McMillan. This formula has been used by Xavier Gourdon with a binary splitting process to obtain more than 100 millions decimal digits of γ in 1999.

---

Here, as usual, H_k denotes the k-th harmonic number, with H₀ = 0, and for positive k,

$H_{k}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}.\,\!$

For example, n = 3 (k = 14) should give an approximation good to more than 10 decimal places, and the computations are relatively easy. One word of advice for those new to numerical methods: for better results sum the terms of a series from smallest to largest. --KSmrq^T 23:32, 8 July 2006 (UTC)

I wrote a naive implementation in Python of the Brent-McMillan formula a while back. It'll calculate a few thousands of digits or so of γ within reasonable time. I'm not sure how they managed to do it with only d digits internally, though, since there's a huge cancellation in (A/B) - log n. Choosing 2d digits seemed to work for my program; more detailed analysis would be welcome.

For very high precision, you'd need to use FFT multiplication and binary splitting of the series. There's also an iterative version, given in Borwein & Bailey, Mathematics by Experiment - Plausible Reasoning in the 21st Century, page 138: Choose n appropriately (details not given), set

$A_{0}=-\log n,B_{0}=1,U_{0}=A_{0},V_{0}=1,$

and for k = 1, 2, ... iterate

$B_{k}=B_{k-1}n^{2}/k^{2},A_{k}=(A_{k-1}n^{2}/k+B_{k})/k$

$U_{k}=U_{k-1}+A_{k},V_{k}=V_{k-1}+B_{k}$

until U and V don't change anymore. Then γ ≈ U/V. I haven't attempted to implement this yet. Fredrik Johansson 00:11, 9 July 2006 (UTC)

Thank you all. I feel for my purposes the iterative process from Fredrik will be most useful. -- He Who Is^{[ Talk ]} 02:33, 9 July 2006 (UTC)

Proof no one (who could achieve it) wants world peace?

1. Assume x can achieve world peace.
therefore (from 1):
1b The only way for x not to achieve world peace, is x must not want it. (Because if he wanted it but couldn't achieve it, 1 would be violated.)
2. X wants world peace.
2b it follows from 1b and 2 that "There is world peace".

However, there isn't world peace. Therefore, there is no x, ie there is no one who can achieve world peace and wants it, and also it follows that anyone who can achieve world peace doesn't want it, and anyone who wants world peace can't achieve it?

I think "there isn't world peace now" is pretty self-evident, but the conclusions in the last paragraph certainly aren't. Is there something wrong with my reasoning? Thank you. 82.131.185.76 16:48, 8 July 2006 (UTC).

What if x can achieve it, and wants to achieve it, but doesn't know it can achieve it? For example, replace "achieve world peace" with "eat food" and assume x is in a room with food, but the food is hidden. 128.197.81.223 17:32, 8 July 2006 (UTC)

The statement "No-one who could achieve world peace wants it" could indeed be true. —Ilmari Karonen (talk) 17:45, 8 July 2006 (UTC)

This makes (at least) one other false assumption: that achieving world peace is one person job, which it almost certainly isn't; imagine if 10 people in the world could each get 10% of the way to world peace, but they never met; although world peace would be achievable, it would never be reached. There are probably thousands of people who want and can help achieve world peace, but there will probably never be enough of them working together. Secondly, 2b does not logically follow from 1b and 2; what does follow is "x is working towards world peace". smurrayinchester^{(User), (Talk)} 17:49, 8 July 2006 (UTC)

to the first response: You can't achieve it if you don't know how to. You can't achieve it if psychological blocks keep you from doing it. You can't achieve it if whenever you start to someone distracts you. Etc. By "able to achieve it" I mean just that. I don't mean physically able, etc. The second response is exactly what I was thinking too: It's like a vote. 2/3 of congress can change the constitution, but the fact that the constitution isn't being changed means (trivially) that no one who can change it is doing so. So, the fact "no one can achieve world peace" must be read very narrowly as meaning "no one can singly achieve world peace instantly upon resolving to do so."

to the vacuous truth person: a vacuous truth isn't LOGICALLY MANDATED, for example "All elephants inside a loaf of bread are pink." is a probably vacuous truth. But not because it's a tautology.

Is it a tautology (not mere vacuous truth) to say: "In the unlikely case that there is currently someone in a position to instantly achieve world peace upon wishing to do so, it logically follows that this person does not currently wish to do so."

Thanks for your analyses! 82.131.185.76 18:25, 8 July 2006 (UTC)

Another factor you've left out of your reasoning is time. It is possible that there is a person which wants world peace, and is capable of achieving it all by himself, but this is a process that could take some time. So, there isn't currently world peace, but he's working on it... But I think the truth here is that there is no person who is able to achieve world peace. It seems unrealistically optimistic to believe that such a person exists. So yes, your conclusion is IMHO true - every person is not able to achieve world peace, including those who want it. -- Meni Rosenfeld (talk) 19:50, 8 July 2006 (UTC)

Another possibility is that those who can achieve world peace do wish to do so, but have decided that the cost is too high. For example, an equitable distribution of the Earth's wealth would bring us a long way toward world peace, but would leave us each with only $9500 GDP per person, which is a huge step down for most people in the developed world. StuRat 20:08, 8 July 2006 (UTC)

Indeed. It takes the idea of "want" a bit simplistically. People do things, or fail to do them, for many reasons at once. You could say that I don't "want" a donut if I choose not to eat it. But what if I said, "I do want to eat it, but I want to stay healthy more." Such a situation is difficult to fit into your framework. As a matter of fact, I would kill for a donut right now, but actually I wouldn't, because killing is wrong. So, do I want the donut, or not? Black Carrot 16:59, 10 July 2006 (UTC)

Three-dimensional coordinate Math system

What is the name of the "z" coordinate in a three-dimensional coordinate math system?

• The x coordinate is called the abscissa.
• The y coordinate is called the ordinate.

I just call it the Z-coord along the Z-axis, myself. Those other silly names do nothing but make math harder, as far as I can tell. If everyone called them the X-axis and Y-axis, instead, we would have two less useless bits of information math students need to learn and they would have more time to learn something of actual importance. StuRat 19:58, 8 July 2006 (UTC)

I agree with StuRat, but either way, there's a good chance no name exists. In polar coordinates there are no such names. The coordinates are merely (t,r) or (Θ,r). Unless you consider "theta" and "radius" fancy names. -- He Who Is^{[ Talk ]} 20:31, 8 July 2006 (UTC)

Let us first consider a larger question. Mathematics routinely deals with larger dimensions. When we have 20 dimensions, how shall we name numbers 17, 18, and 19? And when we have 200? The point is, the specialized names "abscissa" and "ordinate" are of limited utility. The abscissa is where a perpendicular from a plotted point cuts the horizontal axis (think of "scissors").

If we plot a z value that is a function of x and y, then by rights we should drop a perpendicular to the xy plane and call that point the abscissa. More often, we use names special to the problem. For example, in describing the topography of Madagascar, the directions would be called "latitude", "longitude", and "elevation".

The abscissa-ordinate naming scheme has meaning when plotting y as a function of x, but it does not generalize well to name dimensions. In fact, that is not its purpose. These peculiar names, admittedly somewhat archaic, are best used not to refer to the x and y coordinates, but to their roles. We might instead refer to "independent" and "dependent" variables, if not for the fact that we may need to distinguish between the variables themselves and the coordinates on a graph. That is, we might say

• Given a functional dependency y = f(x), we can draw a graph by plotting the independent variable, x, as the abscissa and the dependent variable, y, as the ordinate.

It's hard to say whether these names are retained for utility, blind tradition, or a scholarly fondness for links to the past. Whatever the reason, graphs in higher dimensions need to move beyond them. --KSmrq^T 21:24, 8 July 2006 (UTC)

I would have said :

• Given a functional dependency y = f(x), we can draw a graph by plotting the independent variable, x, along the horizontal axis and the dependent variable, y, along the vertical axis.

This seems to be much clearer and requires no knowledge of archaic mathematical terms. StuRat 01:47, 9 July 2006 (UTC)

Prime Counting Function

In Prime_counting_function#The_Riemann_hypothesis, it says that proving the Riemann Hypothesis true would prove a particular restriction on the prime counting function true as well. Why? Also, does it go the other way? Would proving this restriction true reflect on Riemann's idea?

I don't know enough analytic number theory to really understand why, but I feel like this applet gives me a glimpse. The Riemann Hypothesis is equivalent to that stronger bound, so if you prove one you also prove the other. —Keenan Pepper 20:57, 8 July 2006 (UTC)

One other thing: what's the inverse of x/ln(x)? Some things have said it's xln(x), but I can't find a way to make that work. Black Carrot 20:41, 8 July 2006 (UTC)

Well assuming that's true, we can say that:

${\frac {x\ln(x)}{\ln(x\ln(x))}}=x$

${\frac {x\ln(x)}{\ln(x)+\ln \ln(x)}}=x$

${\frac {x\ln(x)}{\ln \ln(x)}}=x-1$

After putting in a few random inputs, this seems to hold up, but that's not to say that it's actually true -- He Who Is^{[ Talk ]} 04:09, 9 July 2006 (UTC)

How exactly does this absurd formula hold up? In any case, The inverse function of x / ln(x) cannot be expressed with elementary functions, but it can be expressed with Lambert's W function:

${\frac {y}{\ln {y}}}=x\iff y=-x\cdot W\left(-{\frac {1}{x}}\right)$

x ln(x) is a fair approximation though; and you can obtain successively better elementary approximations by repeatedly replacing ln(x) with ln(x ln(x)). The reason is that what you actually seek is y = x ln(y), only that you don't know y. If, instead of y, you put some approximation for y, you will get a better approximation. -- Meni Rosenfeld (talk) 14:35, 9 July 2006 (UTC)

Aha. So, what about the second question? Does proving the restriction prove (or help prove) the Riemann Hypothesis? Black Carrot 17:45, 9 July 2006 (UTC)

Yes, as Keenan mentioned, the article says that the Riemann hypothesis and the tighter bound are equivalent. Proving this bound will immediately also prove the Riemann hypothesis (and vice versa). -- Meni Rosenfeld (talk) 17:58, 9 July 2006 (UTC)

Sorry. I'm fairly new to mathematical discussion, and the code words (conjecture, equivalent, heuristic, etc.) take some getting used to. One further question:

Since the average density of primes around x is close to 1/ln(x), the average distance between primes in the same area is ln(x). However, the integral of this, x(ln(x)-1), is suspiciously similar to the best simple approximation of the x^th prime, xln(x), which is the inverse of the prime counting function, the derivative of which is 1/ln(x). Is there any particular reason for this circle? Black Carrot 16:50, 10 July 2006 (UTC)

That would depend on what you mean by a "particular reason". But how about this: If π(n) is the number of primes up to n, p(n) is the nth prime number, and Δ(n) = p(n+1) - p(n), then Δ(n) is roughly equal to ln(p(n)), which is roughly equal to ln(n) (ln grows slowly enough for this approximation). Then:

$p(n)=p(1)+\sum _{k=1}^{n-1}\Delta (k)\approx \int _{1}^{n}\Delta (k)dk\approx \int _{1}^{n}\ln(k)dk$

Which explains the similarity between the integral of ln(n) and p(n). -- Meni Rosenfeld (talk) 07:32, 11 July 2006 (UTC)

Also, it is mentioned in Von Mangoldt function that von Mangoldt's explicit definition of the summatory von Mangoldt function using a sum over the non-trivial zeroes of the Riemann Zeta function wconstibuted to the first proof of the Prime Number Theorem. If I'm correct, this was the second connection ever found between the prime counting function and the Riemann Zeta function. The first was the sum over the primes p of 1/(1-p^-s) = ζ(s) -- He Who Is^{[ Talk ]} 19:29, 11 July 2006 (UTC)