Wikipedia:Reference desk/Archives/Mathematics/2011 August 15

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.

August 15

"Most"

Can the statement, "Most [partial / nonlinear / etc] differential equations have no analytic solution" be quantified in any way? Obviously it is true, but it seems to come up a lot in textbooks without any further detail. 166.250.65.167 (talk) 00:44, 15 August 2011 (UTC)

No answers for a while, so I'll give one that's only tangentially related. There is the Risch algorithm which tells you which elementary functions have elementary antiderivatives. Once you focus on the class of elementary functions, there are various ways in which you could rigorously define "most", and then (for example) prove that "most" elementary functions do not have elementary antiderivatives (I don't know if that's true actually, or if it's been done). Some similar thing could in theory be done for general DEs, though it would have to be much more complicated. Staecker (talk) 23:29, 16 August 2011 (UTC)

factoring integers

Hi. I have a number 'n' and know its prime factorization. Everything is integers. I seek 'a', 'b' with 'n=ab, a >= b' such that $a/b$ is as close to one as possible. For example, if $n=4896=2^{5}3^{2}17$, I would write $a=2^{3}3^{2}=72$ and $b=2^{2}17=68$, giving a ratio of $72/68=1.0588$. I don't think it's possible to do better. Is this a special case of a more general problem? Are any efficient techniques known for this problem? The numbers I am considering are of the order of a googol Robinh (talk) 01:53, 15 August 2011 (UTC)

Here's one basic method:

              _
S = truncate(√N)
for I = S to 2, step -1
  if N/I is an integer, then
    solution = I and N/I
    stop program
  end
end
N is prime, so no solution found

StuRat (talk) 03:24, 15 August 2011 (UTC)

OK, thanks StuRat. Your method works, but doesn't "use" the prime factorization of 'N'. If 'N' is a googol to within an order of magnitude, and the best answer has a/b=1.1, say, then you'll need to check about $5\times 10^{48}$ suggestions. And, taking a googol minus 10 as a representative example, this has 16 factors counting multiplicity, which would give me just $2^{15}=32768$ options to check. I am just wondering if there is a "nice" way to check these 32768 options, as I can't believe that this problem isn't a commonly encountered one. Thanks again, Robinh (talk) 04:27, 15 August 2011 (UTC)

If you consider the logs of the primes you end up with a problem similar to the partition problem, except that your values aren't integers. According to the article the partition problem is NP-complete so probably there's not a polynomial time algorithm to find the optimum for this problem either. Maybe some of the approximation algorithms would be applicable though. Rckrone (talk) 07:00, 15 August 2011 (UTC)

I was thinking something similar, except with subset sum. The approximation algorithm given there should work with multiplication in place of addition.--Antendren (talk) 07:07, 15 August 2011 (UTC)

The LLL algorithm can also be applied here. Count Iblis (talk) 00:00, 16 August 2011 (UTC)

(OP) Thanks for this, Iblis. I think I see that the page is helpful, but am getting tangled up as to how lattices are relevant here. Could you give me a hint as to how to translate my problem to a form where the LLL algorithm helps? best wishes, Robinh (talk) 09:29, 16 August 2011 (UTC)

You run it as an integer relation algorithm as described in the last paragraph of the article. You then search for a relation between 1/2 Log(n) and the logarithms of the prime numbers. You can implement this easily in Mathematica as follows. We define the function latred[ac,x1,x2,x3,....,xn], where "ac" is the accuracy in decimal digits and the x_r are the real numbers amongst which we seek a relation:

latred[ac_, x__] :=

 Module[{w = 10^(ac), y = {x}, ln, ar}, ln = Length[y]; 
   ar = Table[
       If[r == s, 1, If[s < ln + 1, 0, Floor[w yr]]], {r, 1, ln}, {s, 1, ln + 1}]; LatticeReduce[ar]]

Then if the we apply this to n numbers, the output will be a list of vector of length n+1. The list contains n such vectors. Each vector defines a linear relation between the x_r, the rth components of a vector is the coefficients of x_r such that the sum is zero to witin a tolerance defined by the last component of the vector times 10^(-ac).

You need to experiment with chosing the parameter "ac" correctly. In the case of your example, the following input works:

In[2]:= latred[2, 1/2 Log[4896], Log[2], Log[3], Log[17]]

Out[2]= {{-1, 3, 2, 0, 1}, {-1, 2, 0, 1, -3}, {-2, 0, 0, 3, 1}, {-1, -4, 9, -1, -2}}

The first two output vectors in the list correspond to the numbers a and b that you obtained. Count Iblis (talk) 19:08, 16 August 2011 (UTC)

Thank you Iblis, I see it now.

Resolved

Robinh (talk) 19:40, 16 August 2011 (UTC)

I see this as a version of the knapsack problem. The question states that the prime factors are known. So, you don't really care about the original number. You have the prime factors and you want to arrange them into two groups (knapsacks) such that the product of each group is about the same. In other words, you are trying to fill up one knapsack so you get as close as possible to filling it up. The size of the knapsack will be the square root of the original number. Once you fill it up to the maximum amount possible, the other number will be the original number divided by the product of the primes in the knapsack. I know that the real knapsack problem uses the sum of the items, but switching to the product of the items does not (in my mind) change the problem. So, use any of the solutions in the knapsack problem article. Regardless, this is still an NP-complete problem. -- kainaw™ 19:40, 16 August 2011 (UTC)

Actually, can I retract the resolved tag? The LLL algorithm, unlike the knapsack version, does not account for the fact that I have only a limited number of factors. But I am relieved to discover that it is NP-complete (I have been giving myself a hard time for not being able to solve it quickly). Best, Robinh (talk) 20:08, 16 August 2011 (UTC)

Is the probability of guessing the right number out of N choices one in N^2?

If there were a lottery game where one of 10 balls labeled 0-9 were blindly pulled out of a jar, then when I was guessing before the drawing, there would be a one-in-ten chance that I would guess, say, three. Then, when the drawing was actually done, there would also be a one-in-ten chance that the winning ball would also be three. So there are 100 different combinations (e.g., guess four, draw eight, etc...). So isn't it correct that the probability of you guessing a given number out of N and that number in fact being drawn is one in N^2? You can think of your guessing, or pressing the "easy pick" button, as another separate drawing. 20.137.18.50 (talk) 13:43, 15 August 2011 (UTC)

If you did indeed want to model the guessing with probability as well, the probability of correctly guessing the winning ball is still 1/N. The reason is that there are still N ways in which you can correctly guess the winning ball. To continue with your example, while there are 100 possible outcomes in your experiment, there are 10 outcomes which correspond to you picking the winning ball: guess 0/pick 0, guess 1/pick 1, ..., guess 9/pick 9. If each one of those outcomes has a probability of 1/N^2, the probability of the union of those (mutually exclusive) events is N*1/N^2=1/N. Nm420 (talk) 14:57, 15 August 2011 (UTC)

EC: There are N² ways of the game 'playing out', but N of them result in you winning ('pick x, draw x'), so you have an N in N² chance of winning --- or, 1 in N. Icthyos (talk) 15:00, 15 August 2011 (UTC)

This reminds me of a recent case where a woman had three children with the same birthday (not the same year) - some papers claimed that the probability of this was one in 365*365*365 = 48,627,125, whereas it's actually one in 365*365 = 133,225 (or probably much better than that, as she presumably exercised some choice in the likely range of birth dates). Ah, here's an example. AndrewWTaylor (talk) 17:10, 15 August 2011 (UTC)

Note that it being 365×365 assumes she only has 3 children. With more kids the chances are better. Also it assumed they were completely independent events, and, as you noted, they aren't (perhaps her and her hubby only hook up on their anniversary each year :-) ). StuRat (talk) 17:45, 15 August 2011 (UTC)

You laugh at that. I have friends with three children, all born in the same week nine months after the husband's birthday. --Jayron32 20:29, 15 August 2011 (UTC)

And my mother was born exactly 9 months after the repeal of Prohibition. :-) StuRat (talk) 21:06, 15 August 2011 (UTC)

AndrewWTaylor's example is actually mentioned in the biography of the quoted mathematician, Roger Heath-Brown. I doubt he would make that mistake. I suspect that the paper either gave him another question such as "What is the chance of 3 children being born 7 October?", or that they misunderstood his reply. PrimeHunter (talk) 20:59, 16 August 2011 (UTC)

Riemann?

Hi. I'm taking a theory of knowledge course and one of the major topics is different views of things that are usually considered absolute, such as maths. There is an example given (which unfortunately I do not remember to extreme clarity) in geometry, something about parallel lines. I might not have this exactly right so please correct me if you know what I'm talking about: Anyway, in the Euclidean view of geometry, there are an infinite number of lines parallel to a given one, in the Riemannian view (I think) there is only one, and in another view (I forget) there are none. I am familiar with the Euclidean interpretation, but what are the other ones, and why are there fewer (or no) parallel lines? I'd just like an intuitive overview, I'm not really a mathy person but I'd like to have more knowledge on this. Thanks. 203.117.33.23 (talk) 22:14, 15 August 2011 (UTC)

We have an article, parallel postulate, that might be more useful to you than an attempt at an explanation here. Looie496 (talk) 23:08, 15 August 2011 (UTC)

See also Hyperbolic geometry, especially the section on visualisation (as featured in the works of M. C. Escher), and Elliptic geometry. I first learned about stuff this many years ago from W.W. Sawyer's wonderful "Prelude to Mathematics", which has a nice non-technical treatment of the hyperbolic plane. AndrewWTaylor (talk) 07:47, 16 August 2011 (UTC)

I see there's a Dover reprint now. Yes I agree a very good book, it was the first maths book I ever bought with my saved up pocket money when I was twelve, I kept it hidden from everybody and still have it. Dmcq (talk) 08:52, 16 August 2011 (UTC)