Mathematics desk
< December 21	<< Nov \| December \| Jan >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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 22

Random pi convergence

Suppose you wanted to test whether or not a stream of bits was likely generated by a random process. So you construct K pairs of N-bit numbers, then count the number of pairs that are coprime. The percentage should approach 6/pi^2. But just how many trials would be needed to obtain a given number of significant digits? Is it even guaranteed to converge? Earl of Arundel (talk) 00:54, 22 December 2020 (UTC)[reply]

As a randomness test this method is somewhat peculiar. Anyway, no, there is no guarantee of convergence. It is not clear from the question whether just K goes to infinity, or both K and N with the value of N depending on K. In either case, an adversary can generate a stream of bits which, chopped up into pairs of N_K-bit numbers, results in a stream of pairs which are all either (2, 2) or (2, 3). This can then be compressed into a stream of truth values (T or F), corresponding to the coprimality status of these pairs. The adversary can choose the original bitstream so that the first 10 outcomes are T, the next 100 are F, the next 1000 are T, and so on, alternating between T and F for ever larger segments. The fraction of Ts will keep oscillating between 1/11 and 10/11. --Lambiam 07:30, 22 December 2020 (UTC)[reply]

Right, as K goes to infinity. N just limits the overall accuracy, I think. If you scaled up to 32768 bits you'd get many more significant digits than say 8 bits. But I see your point. You would have to approach the data from several more directions at the very least. This "test" then really just tells you that the data looks random in some limited way. Maybe a building block for a test, but hardly robust enough to make any convincing arguments either way. So I guess that clears things up. As always, I do appreciate your insightful analysis, Lambiam. Cheers! Earl of Arundel (talk) 17:58, 22 December 2020 (UTC)[reply]

Let me add that a sender, using modern cryptological methods, can make a meaningful message appear so random that no test will reveal that it actually is not. --Lambiam 18:32, 22 December 2020 (UTC)[reply]

Sounds like making any sense of the data is the real challenge! So maybe not so much for verification purposes. Earl of Arundel (talk) 12:54, 23 December 2020 (UTC)[reply]

Either way there is also the infinite monkey theorem. --2600:1700:90E0:E040:754C:160A:85F8:F630 (talk) 20:47, 22 December 2020 (UTC)[reply]

Are you an infinite monkey? How is this relevant? --Lambiam 21:37, 22 December 2020 (UTC)[reply]

Request for someone to make an svg

The page Kinetic_energy#Relativistic_kinetic_energy_of_rigid_bodies contains the following formula:

E_{\text{kinetic}}=\int \mathbf {v} \cdot d(m\gamma \mathbf {v} )=m\gamma \mathbf {v} \cdot \mathbf {v} -\int m\gamma \mathbf {v} \cdot d\mathbf {v}

This step if very hard to understand mathematically but visually has a simple and obvious explanation. If I had a svg showing the function $m\gamma \mathbf {v}$ as a function of v (not log-log) then I could turn it sideways to get v as a function of $m\gamma \mathbf {v}$ and I could show how that step is derived. (m is a constant and can be ignored). I have inkscape but no way of drawing a math function. Is there somewhere I could request for someone to make such an svg? It would also have to show how it defers from the classical mv as a function of v. Just granpa (talk) 12:56, 22 December 2020 (UTC)[reply]

This is an application of integration by parts, compactly rendered by the general formula

\textstyle \int udv=uv-\int vdu.

It is not hard to understand if you use the product formula for a differential:

d(uv)=udv+vdu,

which can be rearranged as

udv=d(uv)-vdu.

Integrating both sides, using

\textstyle \int d(uv)=uv,

gives the integration formula. The article on the technique shows a visualization of the kind you suggested. --Lambiam 13:54, 22 December 2020 (UTC)[reply]

Thank you. Just granpa (talk) 14:28, 22 December 2020 (UTC)[reply]

procedure using rationals are dense

It should be easy to do this, and it is easy to prove it can be done, but I can't define an easy way to do it:

Let a be an irrational number (it's trivial if it's rational) and b an arbitrarily small positive rational number. What is a procedure to return 2 distinct rational numbers from the interval (a,a+b) ?

(There might be a way that starts calculate a rational approximation b*ceil(a/b) but I'm not sure and I think there should be something better...)

Thank you, RJFJR (talk) 20:40, 22 December 2020 (UTC)[reply]

I don't think it's possible to give an answer until you explain how the irrational number a is presented. The obvious setup would be to think of your procedure as a program in a language that has an oracle that gives, say, decimal digits of a, or otherwise gives arbitrarily good rational approximations to a, but then the problem is trivial, so you must be asking something else. What are you asking exactly? --Trovatore (talk) 21:30, 22 December 2020 (UTC)[reply]

If you have a procedure to produce one rational value in the interval (a, a+b) for arbitrary positive rational b, then you can also produce one for b/2, b/3, and so on, and the sequence of numbers thus produced contains a descending subsequence that converges to a – which gives an infinity of rationals between a and a+b. As Trovatore says, it is not possible to give a procedure independent of the presentation. Here is a similar but seemingly much simpler problem: Given a real number a, produce an integer i such that i > a. It sounds trivial, but it is not. An even simpler problem, but only seemingly: Given a real number a, report whether a > 0. If you have a procedure for doing that, I can solve the original problem (assuming I may appeal to Markov's principle). --Lambiam 22:04, 22 December 2020 (UTC)[reply]

If one is allowed to use the ceiling function, as suggested in the question, the problem is not hard to solve, using the property that x ≤ ceil(x) < x + 1. Let n be a sufficiently large positive integer – how large it needs to be, we'll see later. Then, by the property of the ceiling function, na ≤ ceil(na) < na + 1. Take c = ceil(na)/n, so by dividing everything in the inequation by n, we obtain a ≤ c < a + 1/n. Since a is irrational, the first inequality is strict: a < c < a + 1/n, or, equivalently, c ∈ (a, a + 1/n). We are almost done; all we need is to pick a value for n such that 1/n ≤ b. That is easy: take n = ceil(1/b). --Lambiam 22:50, 22 December 2020 (UTC)[reply]

If you take the infinite expansion of an irrational number a as a continued fraction – which can be computed if you can use the ceiling function and therefore the floor function – and take every second approximant (the second, the fourth, and so on), this gives a descending sequence of rationals that converges to a. For example, for π, that descending sequence goes like 22/7, 355/113, 104348/33215, 312689/99532, ... . For an approximant p/q in that sequence (in simplified form), it is the case that a − p/q < 1/q². So all approximants p/q for which q² ≥ 1/b satisfy a < p/q < a + b. --Lambiam 07:38, 23 December 2020 (UTC)[reply]

Thanks everyone. By procedure I didn't mean a computer subroutine, I meant the kind of description they give in a math book, and I should have said ceiling instead of ceil (I was distracted by realizing I don't know the wikimarkup for the math extension to do that little right angle upsidedown L for ceiling.) The answer about sufficiently large n and how to determine it is sufficiently large is the kind of thing I was looking for. Thank you. RJFJR (talk) 19:39, 23 December 2020 (UTC)[reply]

The markup for the math extension is standard LaTeX: <math>\lceil x\rceil</math>, which renders as

\lceil x\rceil

. Or you can use Unicode characters, as in ⌈''x''⌉, which renders as ⌈x⌉. The amputee brackets actually have character entity references that are not difficult to remember: you can use &lceil;''x''&rceil; instead. --Lambiam 20:41, 23 December 2020 (UTC)[reply]

Lambiam, I was confused by your first answer and hoped you could clarify it without taking this too far off topic.

Had RJFJR simply wanted to posit two distinct rational numbers in their interval, they could have done so "using rationals are dense" in that it can be used to show that there are infinitely many rational numbers in the interval, and simply ... "let q₁ and q₂ be two such rationals." (That doesn't even invoke the Axiom of choice.)

However that won't do if RJFJR's "procedure to return ..." meant a description which could be converted into an algorithm to compute their values given a and b. The obvious answer then is a formula involving the ceiling function. (As with your second answer.)

But in your first answer you wrote that, "it is not possible to give a procedure independent of the presentation." How is a formula in a and b involving the ceiling function not independent of presentation?

You also wrote "Given a real number a, produce an integer i such that i > a. It sounds trivial, but it is not." What's wrong with i = ⌈a⌉ + 1?

As for "Given a real number a, report whether a > 0", > is a well defined relation on ℝ, so "If a > 0 then a > 0." Perhaps a tautology is unsatisfying, but what more do you want?

I suspect that we are down to semantics here, or possibly we're playing with the foundations of logic or mathematics and I'm taking too simplistic a view. -- ToE 17:18, 27 December 2020 (UTC)[reply]

It is a matter of different mathematical frames. I interpreted the original question in terms of effective computability. We have an article on computable numbers, which are real numbers, We also have an article on computable functions, but it does not deal with computable functions on the real numbers. Let me define, somewhat sloppily, such functions as functions that, given computable numbers for their arguments, return a computable number. To be more precise we need to fix the way (computable) reals are presented, in the form of a number describing an algorithm (such as the identifier of Turing machine; any of a variety of seemingly different but ultimately equivalent approaches will do). Then, given such presentations as input, the function needs to return a presentation for the result. As stated in Computable number § Properties as a field, the usual arithmetical operations are computable, and so are the absolute value function and trigonometric functions. However, functions that have a discontinuity in their domain, such as the sign function, are not computable. If they were, this would solve the halting problem. The floor and ceiling functions are not continuous and therefore not computable. If you want to have an effective procedure then the method using the ceiling function works fine for floating point numbers, which are in fact rational numbers, but not in general. --Lambiam 22:54, 27 December 2020 (UTC)[reply]

Digression: You need a bit more than that to define computable functions on computable numbers. Let's just fix the "presentation" to say that a computable real is represented by a program that produces an effective Cauchy sequence; say, the program accepts a natural number n and returns a rational number p(n)/q(n), such that for any n, m, the difference between p(n)/q(n) and p(m)/q(m) is less than 1/n.

Now to define a computable function on these, you need a program that, given a program for computing an effective Cauchy sequence as above, gives you a program for computing another effective Cauchy sequence, plus one more thing: The second real number needs to depend only on the first real number, not on the specific effective Cauchy sequence or the specific program used to compute it.

This last criterion (which we can call "extensionality" if you like) is a little tricky to consider in the computable framework. Harking back to an earlier discussion, this is why I am doubtful that there is a computable injection from the computable reals into the natural numbers. --Trovatore (talk) 21:21, 28 December 2020 (UTC)[reply]

That is why I wrote "somewhat sloppily". I hope I did not suggest that there is a computable injection from the computable reals into the naturals. It would give us the effective decidability of equality on the computable reals. --Lambiam 23:16, 28 December 2020 (UTC)[reply]

Actually, it does not work fine on floating point numbers. In a given system of floating point arithmetic, such as described by IEEE 754, there is a largest number a such that a < 1. Taking b to be 1 − a, there is no daylight between a and a + b. --Lambiam 23:03, 27 December 2020 (UTC)[reply]

Interesting. I had almost joked that you seemed to be treating ceiling as a second-class function ... and in a way you were! I suppose it was RJFJR's use of "procedure" which shifted frames for you. Likewise my "description which could be converted into an algorithm to compute their values" -- I should have stuck with "formula". -- ToE 13:53, 28 December 2020 (UTC)[reply]

But if you're going to use "formula", then why not just define a function that provides what RJFJR was asking for, and give it a name by fiat? Define foo(a, b) to be the rational number with smallest denominator (when reduced to least terms) in the interval (a, a+b), with any ties broken by using the smallest numerator. Now the answer to RJFJR's question is given by the function symbol foo, whose interpretation is well-specified.

That's why Lambiam and I (or at least I; maybe I shouldn't speak for Lambiam) looked for some other implicit meaning in the question. --Trovatore (talk) 20:19, 28 December 2020 (UTC)[reply]