Wikipedia:Reference desk/Archives/Mathematics/2010 February 23

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.

February 23

98765321 / 1233456789

98765321 / 1233456789 —Preceding unsigned comment added by 71.143.224.27 (talk) 05:08, 23 February 2010 (UTC)

What is your question? Any calculator will give you a value of about 0.8. Are you wondering why there are two 3's in the denominator? Are you wondering what / means? Are you wondering why your computer didn't instamagically speak the answer to you when you randomly typed numbers into some random website that you stumbled upon? -- kainaw™ 05:17, 23 February 2010 (UTC)

Perhaps it was a typo and the OP meant to ask about the progress of the sequence 1₂/1₂, 21₃/12₃, 321₄/123₄, 4321₅/1234₅, ..., specifically the fact that $\lim _{b\to \infty }{\frac {1}{b-2}}{\frac {\sum _{n=1}^{b}nb^{n-1}}{\sum _{n=1}^{b}nb^{b-n}}}=1$. 58.147.60.130 (talk) 06:50, 23 February 2010 (UTC)

I thik they probably duplicated the 3 in the second number. Perhaps this is some sort of alien maze test on the reference desk to see how it scurries around when presented with random stuff? I've noticed mopre and more of these type questions where they just enter some random search query with random keywords as if querying google. I think the answer is they should enter it into google. Dmcq (talk) 12:07, 23 February 2010 (UTC)

One sometimes sees it mentioned that 123456789 × 8 = 987654312, just because the pattern in the digits is amusing. Michael Hardy (talk) 13:26, 23 February 2010 (UTC)

Problem 323 in The Moscow Puzzles by Boris A. Kordemsky presents the following four numbers, each of which is an arrangement of the ten digits 0 through 9:

2,438,195,760; 4,753,869,120; 3,785,942,160; 4,876,391,520.

Each of these numbers is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, and 18. —Bkell (talk) 22:52, 23 February 2010 (UTC)

As long as we're on this topic, this one's cute:

12 345 679 × 81 = 999 999 999

(Note: 12345679, with NO 8.) Michael Hardy (talk) 23:19, 26 February 2010 (UTC)

Inversion in a Galois Field

Hello, for a computer science project, I am looking for an algorithm that will invert any given element (zero maps to zero) in the Galois Field GF(2^128) and give me its multiplicative inverse. The problem is that my background in abstract algebra/number theory is very limited (one undergrad course in each) so can anyone please point me to a good resource on the internet that I can use to write my own source code. Something fast and efficient preferably. If somebody has an m file laying around that already does this or if someone known how to do this on MATLAB for example, it would be appreciated. This is just one of the steps in a larger scheme. Oh and I also have an irreducible polynomial given as the modulus. Thanks! 174.29.98.151 (talk) 07:10, 23 February 2010 (UTC)

If you just want a straightforward implementation, use the extended Euclidean algorithm. If you want highly optimized code, web search on "finite field inversion". A huge amount of work has been done to optimize that operation, for elliptic curve cryptography and other reasons. 75.62.109.146 (talk) 07:22, 23 February 2010 (UTC)

Woah, that works for all finite fields? I thought it only worked for $\mathbb {Z} /n\mathbb {Z}$. 174.29.98.151 (talk) 07:29, 23 February 2010 (UTC)

How do you represent the finite field F = GF(p^d) with p prime? You fix an irreducible polynomial f(x) over $\mathbb {Z} /p\mathbb {Z}$ of degree d, you define F to consist of all polynomials of degree less than d, you add them as usual, and you multiply them modulo f. Computing an inverse in F then amounts to computing an inverse polynomial modulo f, and that's what the extended Euclidean algorithm (for polynomials in $(\mathbb {Z} /p\mathbb {Z} )[x]$, not for integers) does. In order to implement it, you have to do computations in $\mathbb {Z} /p\mathbb {Z}$, and in particular to compute inverses in $\mathbb {Z} /p\mathbb {Z}$ you'll also need the extended Euclidean algorithm, this time for integers. But these two are separate issues.—Emil J. 11:43, 23 February 2010 (UTC)

Bijection

Let's assume that our domain of discourse is the set of real numbers.

So, is Ln(X^2) a bijection between the set of positive numbers and the domain of discourse?

Let me explain my question:

On one hand, Ln(X^2) does seem to be a bijection between the set of positive numbers and the domain of discourse, because for every two positive numbers, a,b, if Ln(a^2)=Ln(b^2) then a=b.

On the other hand, Ln(X^2) does not seem to be a bijection between the set of positive numbers and the domain of discourse, because if Ln(k^2) is a number belonging to the domain of discourse, then k is unnecessarily a positive number!

I have a technical question about either option which will turn out to be true:

On one hand, if the first option is correct, and Ln(X^2) is really a bijection between the positive numbers and the domain of discourse, although when Ln(k^2) belongs to the domain of discourse then k is unnecessarily a positive number, then how should I briefly express the fact that: f(X) is a bijection between the set A and the domain of discourse, so that every k (belonging to the domain of discourse) is correspondent - by the inverse correspondence of f - to a single number, and this number belongs to A?

On the other hand, if the second option is correct, and Ln(X^2) is not a bijection between the set of positive numbers and the domain of discourse, because if Ln(k^2) is a number belonging to the domain of discourse then k is unnecessarily a positive number, then how sould I briefly express the fact that: f is a function, whose domain is A, and whose image is the domain of discourse (i.e. f is on the range), so that for every two numbers a,b belonging to A, if f(a)=f(b) then a=b?

HOOTmag (talk) 09:23, 23 February 2010 (UTC)

$\ln(x^{2})$ by itself is not a function. To define a function you need to specify its domain. Usually it is understood that the domain is implicitly specified to be the largest domain possible for the expression, but in your question this seems to be a source of confusion. The function $f:(0,+\infty )\to \mathbb {R} ,x\mapsto \ln(x^{2})$ is injective, while $g:\mathbb {R} \backslash \{0\}\to \mathbb {R} ,x\mapsto \ln(x^{2})$ is not. They are both surjective, and thus f is bijective. -- Meni Rosenfeld (talk) 09:47, 23 February 2010 (UTC)

By "bijection" I meant "one to one correspondence". I'm unnecessarily talking about a function, although every one to one function is also a one to one correspondence.

A correspondence, as well as a one to one correspondence, must have a domain of discourse. In our case, the domain of discourse is the set of real numbers.

My question is about how to interpret the phrase "one to one correspondence between A and B".

Does the phrase "one to one correspondence between A and B" mean that every a belonging to A may indeed be correspondent (by that correspondence) to many elements, of which one single element only - is in B, and that every b belonging to B may indeed be correspondent (by the inverse correspondence) to many elements, of which one single element only - is in A, or: does the phrase "one to one correspondence between A and B" mean that every a belonging to A is correspondent (by that correspondence) to one single element b only, and that b is in B, and that every b belonging to B is correspondent (by the inverse correspondence) to one single element a - only, and that a is in A?

The same question may be asked about a "one to one function between A and B": Does it mean that every b belonging to B is correspondent (by the inverse correspondence) to many elements, of which one single element only - is in A, or: does the phrase "one to one function between A and B" mean that every b belonging to B is correspondent (by the inverse correspondence) to one single element a - only, and that a is in A?

HOOTmag (talk) 12:25, 23 February 2010 (UTC)

Have you read Binary relation? The larger universe (or domain of discourse) has no impact on the characteristics (injective, surjective, bijective, etc.) of a correspondence or function. As Meni Rosenfeld stated above, a function is defined by its domain, its range, and a rule mapping between them; changing the domain or range can change characteristics of the function because it means defining a new function, even it that new function seems a natural extension of the old one. Likewise a correspondence between sets A and B does not depend on the larger universe. So when you speak of a correspondence between A and B it makes no sense to talk of a corresponding to b if a is not an element of A or if b is not an element of B. There may be what seems to you a natural extension of the correspondence to a larger universe, but that is immaterial for considerations of the correspondence itself. 58.147.60.130 (talk) 15:23, 23 February 2010 (UTC)

Also, when you write "correspondence", do you mean a "binary relation that is both left-total and right-total" as defined in Binary relation#Special types of binary relations? 58.147.60.130 (talk) 16:01, 23 February 2010 (UTC)

Note that you may define a function $f:\mathbb {Z} \to \mathbb {Z}$ by $x\mapsto x+1$, or $x\mapsto 1+x$, or $x\mapsto x\cos(2\pi x)+1$, and it is all the same function. Were you to expand the domain and range onto the reals, then using the first two rules would give you a bijection; using the third rule would not. This does not change the fact that $f$ with its original domain and range is bijective if defined by any of the the three rules, because with that original domain the rules are equivalent. 58.147.60.130 (talk) 16:01, 23 February 2010 (UTC)

Let's put it this way: F is a function, and A,B,C are sets. Is there a simple phrase expressing the following two pieces of information (at once)?

When the domain of F is taken to be A, and the codomain of F is taken to be B, then:

1. For every a,b belonging to the domain of F, if F(a)=F(b) then a=b.
2. The image of F is C.

Do you see now my problem? If I simply say that F is a surjective from A onto C (thus informing that C is the image of F), then I miss the first information (i.e. the information that when the domain of F is taken to be A, and the codomain of F is taken to be B, then: for every a,b belonging to the domain of F, if f(a)=f(b) then a=b). However, if I simply say that F is a bijection between A and C (or is an injection from A to B, or to C), then I miss the second information (i.e. the information that when the domain of F is taken to be A, and the codomain of F is taken to be B, then the image of F is C).

HOOTmag (talk) 17:35, 23 February 2010 (UTC)

I am trying, but no, I am not seeing your problem yet. For a function to be bijective is equivalent to it being both injective and surjective. So saying that $f:D\to B$ is a bijection satisfies both your 1. and your 2. What am I missing? If $f:D\to A$ and $B\subseteq A$, then saying that the image of $f$ is $B$ is equivalent to saying that $f$ with its codomain restricted to $B$ is surjective. (I doubt that this is the problem, but you do know, don't you, that a one-to-one function is another name for an injective function, but a one-to-one correspondence is another name for a bijective function.) 58.147.60.130 (talk) 18:05, 23 February 2010 (UTC)

You've replied to an old version of my question. I'd changed my question before you answered (but after you saw the old version). Please review my question again. Anyways, If I simply say that F is a bijection between A and C (or is an injection from A to B, or to C), then I miss the second information, i.e. the information that when the domain of F is taken to be A, and the codomain of F is taken to be B, then the image of F is C. HOOTmag (talk) 18:18, 23 February 2010 (UTC)

Do you agree that if f is a bijection (or even just a surjection) from A to C then then C is the image of any function f redefined by simply changing its codomain? (The codomain of a function is always a superset of its image.) If so, then doesn't saying that f is a bijection between A and C give your second statement? Likewise, if you take any function f from A to B and restrict the codomain of the function to the image, then that new function is surjective. Are we still chasing each other in circles here? Rereading you question 3 outdents above, yes, saying that f is a surjective function from A onto C gives you item 2. but does miss item 1. Saying that f is a bijection from A to C gives 1. (because bijection implies injection) but it also gives you 2. (because bijection implies surjection). (Note the comment in my previous reply about the ambiguities of one-to-one.)58.147.60.130 (talk) 18:48, 23 February 2010 (UTC)

I don't accept your first assumption, because changing the codomain may change the image. For example, when the domain is the set of positive numbers, and F(x) is defined to be the number whose absoloue value is x, then the image of F is the set of positive/negative numbers - when the codomain is the set of positive/negative numbers respectively. Hence, the image is dependent on the codomain (not only on the domain).

To sum up, if I simply say that F is a bijection between A and C (or is an injection from A to B, or to C), then I miss the information that when the domain of F is taken to be A, and the codomain of F is taken to be B, then the image of F is C.

HOOTmag (talk) 21:21, 23 February 2010 (UTC)

There is a slippery semantic slope (one that I may have already crossed) to beware of when speaking of redefining a function by changing its domain or codomain, because, as Meni Rosenfeld pointed out, they are integral to the definition of the function. (See Binary relation#Is a relation more than its graph?) When I spoke of redefining the codomain I was implying that both the "before" and "after" codomains were subsets of some larger codomain where we had still defined a function, but as you point out this need not be the case.

Consider your inverse absolute value binary relation on the reals so that x inv_abs y iff x = abs(y). This is not a function because 1. it is not left-total (there is no y so that -1 inv_abs y) and 2. it is not functional (2 inv_abs 2 and 2 inv_abs -2). If we restrict the domain to the positive reals (as you suggested) it becomes left-total. If we then restrict the codomain to either the positive reals or the negative reals it becomes functional and is in fact a bijection. 58.147.60.130 (talk) 02:25, 24 February 2010 (UTC)

(←)So I believe that I do get a sense of where your unease originates, but I think that with precise language no contradiction appears. I have reread this section, and I believe that all your questions, as stated, are properly answered "bijection". So can you precisely restate your problem with a well defined function or relation? I suggest that for clarity we stick with terms such a function, relation, domain, codomain, injection, surjection, and bijection, avoiding the terms correspondence, range, one-to-one, and domain of discourse unless we specifically define them here. (I have been guilty of using range as a synonym for codomain instead of image -- a minority usage that I will eschew.) 58.147.60.130 (talk) 02:25, 24 February 2010 (UTC)

It seems what HOOTmag has in mind is not a function or a relation, but rather a formula. For example, the formula $\varphi (x,y)=(|y|=x)$. Given a domain A and codomain B, the formula induces a relation $\{(x,y)|x\in A,y\in B,\varphi (x,y)\}$. The question is about the property of $\varphi$, "The relation induced by $\varphi$ from A to B is bijective from A to C". This looks like a short way to describe it, but any shorter one will depend on a convention for denoting the induced relation, of which I am not aware. -- Meni Rosenfeld (talk) 08:30, 24 February 2010 (UTC)

Given two sets X and Y, we say they are one to one correspondent if there's a subset C of XxY (cartesian product) such that the following are satisfied:

For every x in X, there's an order pair with x as 1st coordinate, for any two ordered pairs w,t in C, if they have the same first coordinate then they have the same second coordinate (these two conditions guarantee that it's a function, not a relation).

For every w,t in C, if they have the same second coordinate then they have the same first coordinate (this is for injection). For every y in Y, there's an ordered pair in C with y as second coordinate (this is for surjection).

Now when we say a function from X to Y we mean just like what 58.147.60.130 said; it's an ordered triplet (X,Y,G), where G is a subset of XxY that's a function. Such a function is said to be a bijection if it satisfies the condition I mentioned above. If it helps you can think of when the phrase "A and B have the same cardinality" as a relation between sets, rather than a function. So when we change the codomain Y to Z, we must make sure G is still a subset of XxZ and is still a function. In actually defining G we use a formula like what Rosenfeld said. Money is tight (talk) 15:54, 24 February 2010 (UTC)

Exponential function

I have seen e defined as limit of (1-1/n)^n as n-->∞, but from this definition how one arrive at the equation e^x=lim(1+x/n)^n as n-->∞. I've googled it, but couldn't find a proof anywhere. —Preceding unsigned comment added by 173.179.59.66 (talk) 12:10, 23 February 2010 (UTC)

One way of seeing it is:

$e^{x}=[\lim _{n\to \infty }(1+{\frac {1}{n}})^{n}]^{x}$

$=\lim _{n\to \infty }[(1+{\frac {1}{n}})^{n}]^{x}$

$=\lim _{n\to \infty }(1+{\frac {1}{n}})^{nx}$

$=\lim _{n\to \infty }(1+{\frac {x}{nx}})^{nx}$

$=\lim _{m\to \infty }(1+{\frac {x}{m}})^{m}$

Where the last step is substituting m = nx. The first step can be justified by continuity of exponentiation, and the last step is only justified if we recognize that the limit is taken over the entire real numbers, as opposed to just over the integers. --COVIZAPIBETEFOKY (talk) 13:07, 23 February 2010 (UTC)

Two books you might look at are

• Walter Rudin's Principles of Mathematical Analysis;
• Leonhard Euler's Introductio in Analysin Infinitorum.

Note that it's

$e=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}$

with "+" rather than "−".

Also, you can make "COVIZAPIBETEFOKY"'s TeX display look better by doing it like this:

${\begin{aligned}e^{x}&=\left[\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}\right]^{x}\\[6pt]&=\lim _{n\to \infty }\left[\left(1+{\frac {1}{n}}\right)^{n}\right]^{x}\\[6pt]&=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{nx}\\[6pt]&=\lim _{n\to \infty }\left(1+{\frac {x}{nx}}\right)^{nx}\\[6pt]&=\lim _{m\to \infty }\left(1+{\frac {x}{m}}\right)^{m}.\end{aligned}}$

Michael Hardy (talk) 13:18, 23 February 2010 (UTC)

Also, I suggest you the following alternative path.

1. Prove that for all real x the sequence (1+x/n)ⁿ (n a positive integer) is eventually increasing; precisely, as soon as n>-x (use the inequality between the arithmetic and geometric means).

2. Prove that it is bounded (just observe that 0≤(1+x/n)ⁿ(1-x/n)ⁿ≤1 as soon as n>|x| and use 1).

3. Therefore it converges for any real x: define exp(x) to be the limit of (1+x/n)ⁿ as n tends to infinity.

4. Prove that if x_n→x then also (1+x_n/n)ⁿ→exp(x).

5. Use 4 to prove exp(x)exp(y)=exp(x+y) for all x and y, which justifes the notation exp(x)=e^x.

6. Prove that exp:R→R₊ is increasing and bijective, define the inverse to be log(x) ("natural logarithm").

7. Prove that log(x)=∫₁^x dt/t for all x>0.

8. Prove that exp(x) is the sum of the exponential series.

(...) --pma 16:13, 23 February 2010 (UTC)

In 5 it should be exp(x+y)=exp(x)exp(y), of course. -- Meni Rosenfeld (talk) 16:47, 23 February 2010 (UTC) whatth...corrected! --pma 20:56, 23 February 2010 (UTC)

Square roots

How would I be able to approximate a square root, like (5.23)^.5, with a taylor series. I know the Taylor series for (1+x)^(1/2), but that only converges for 0<x<1... —Preceding unsigned comment added by 173.179.59.66 (talk) 12:49, 23 February 2010 (UTC)

Well you can always approximate the square root of the inverse of x and then invert again as the series converges for |x| < 1. The convergence will be slow though. Why do you want to do it and why is using the Taylor series important since most any calculator will give the result? Dmcq (talk) 13:07, 23 February 2010 (UTC)

You might expand about the point 5.29 = 2.3² rather than about 0. Michael Hardy (talk) 13:30, 23 February 2010 (UTC)

See also Methods of computing square roots#Taylor series. -- Meni Rosenfeld (talk) 13:34, 23 February 2010 (UTC)

You could also divide the operand by four first: the square root of 5.23 is equal to the product of the square root of four (2) and that of 5.23/4 = 1.3075. In that case, the x in the Taylor series is 0.3075, so that would converge. 83.81.42.44 (talk) 19:49, 25 February 2010 (UTC)

The square root of 5.23 was just an example. Actually, I question was inspired by how calculator's are able to evaluate roots, which I believe is through a Taylor series. Is there a way to write a taylor series for the expression (a+x)^1/2?

A calculator almost certainly would not use the Taylor series. That article Methods of computing square roots says calculators would normally do it via log and exp. Dmcq (talk) 23:06, 23 February 2010 (UTC)

Ooh okay, didn't see that article. But one last question (to make sure that I understand Taylor series), is the equation

${\sqrt {N^{2}+d}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!d^{n}}{(1-2n)n!^{2}4^{n}N^{2n-1}}}=N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}}}+{\frac {d^{3}}{16N^{5}}}-{\frac {5d^{4}}{128N^{7}}}+\cdots$

exact for all d<1? —Preceding unsigned comment added by 173.179.59.66 (talk) 02:33, 24 February 2010 (UTC)

It's exact for all $-N^{2}<d<N^{2}$. Anyway, an excellent and simple way to compute square roots is the Babylonian method. -- Meni Rosenfeld (talk) 07:31, 24 February 2010 (UTC)

Integration

How to integrate e^sin(x)? Chirsgayle (talk) 16:36, 23 February 2010 (UTC)

This function has no elementary antiderivative. You can still calculate definite integrals of it numerically. -- Meni Rosenfeld (talk) 16:44, 23 February 2010 (UTC)

You can also calculate antiderivatives of it numerically. E.g. Runge–Kutta or the like. Michael Hardy (talk) 17:46, 23 February 2010 (UTC)

Just curious, but is there any way to show that a particular function, such as the one given here, has no elementary antiderivative, or is it simply a matter of not being able to come up with one using know methods if integration? 58.147.60.130 (talk) 19:39, 23 February 2010 (UTC)

I believe the Risch algorithm can be used for this. -- Meni Rosenfeld (talk) 20:30, 23 February 2010 (UTC)

Very cool. Thank you. 58.147.60.130 (talk) 12:01, 24 February 2010 (UTC)

You don't need to do numerical integration just because there is no elementary antiderivative. You may use a convergent Taylor series. $\int e^{\sin x}dx=\int \sum _{n=0}^{\infty }{\frac {(\sin x)^{n}}{n!}}dx=$ $\sum _{n=0}^{\infty }{\frac {\int (\sin x)^{n}dx}{n!}}$

Bo Jacoby (talk) 13:30, 25 February 2010 (UTC).

...and then evaluate the sums numerically? Seems to me it's still numerical. Michael Hardy (talk) 18:27, 25 February 2010 (UTC)

No, the terms of the sum involve only the elementary antiderivatives $\scriptstyle {\int (\sin x)^{n}dx}$. This is not numerical integration like Runge–Kutta. Bo Jacoby (talk) 06:30, 27 February 2010 (UTC).

Digit by digit root calculation

The method for calculating square roots at Methods_of_computing_square_roots#Digit_by_digit_calculation is currently blowing my mind -- although my friends are less impressed having apparently learned it in grade school. At any rate, what is the proof that it works? Also, I see that it can be generalized to nth roots, when n is an integer -- which lets you calculate nth roots when n is rational -- is there any way to generalize again so a similar method can produce roots for any real number? —Preceding unsigned comment added by 71.70.143.134 (talk) 23:04, 23 February 2010 (UTC)

It's easy to see why this is true, but for a rigorous proof you need to be careful with respect to the decimal point (and perhaps some induction). It boils down to having a current guess p and wanting to find x such that $(p+x)^{2}=S$ which means $p^{2}+2px+x^{2}=S$ or equivalently $(2p+x)x=S-p^{2}$. $S-p^{2}$ is what is denoted there c, and $(2p+x)x$ corresponds to $(20p+x)x$ (up to the decimal point). Since you want only one digit at a time, you take the greatest digit x for which $(2p+x)x\leq S-p^{2}$.

I don't think it can be generalized to irrational-order roots in any meaningful way. Using exp and log is the way to go for general powers. -- Meni Rosenfeld (talk) 07:43, 24 February 2010 (UTC)

You could just approximate n by a rational r, and then compute the rth root. If you're going digit-by-digit then just make r so close to n that the rth root and the nth root match at the digit you're computing. Staecker (talk) 14:43, 24 February 2010 (UTC)