Wikipedia:Reference desk/Archives/Mathematics/2011 February 13

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 13

First d Decimal Places

So here is the problem I am looking to solve. I am given two positive integers k and d and what I do is that I take the square root of k, discard the integer part, and take the first d integers after the decimal point and call it a while discarding the rest, meaning

$a=Floor(10^{d}({\sqrt {k}}-Floor({\sqrt {k}}))$

for example if k=20 and d=6, then a=472135. My question is, if I know d (could be very large compared to k, like 50 decimal places for k=20) and I know a, is there anyway for me to reconstruct k? I was thinking something like suppose I know that a=472135 and d=6, then I have that

$Floor(10^{d}({\sqrt {k}}-Floor({\sqrt {k}}))=472135$

$472135\leq 10^{d}({\sqrt {k}}-Floor({\sqrt {k}}))<472136$

$0.472135\leq {\sqrt {k}}-Floor({\sqrt {k}})<0.472136$

but after that I can't get anything meaningful out of this. I have bounds on the fractional part of the square root of k but how can I get k out of this. I tried squaring but it doesn't do anything for me. Any help would be appreciated. Thank you!174.29.78.245 (talk) 02:25, 13 February 2011 (UTC)

It can't be done. You have lost too much information to be able to recontruct it. Consider, for example, d=1. k=2 and k=6 both result in a=4. That means that, given d=1 and a=4 there is no way to know if you started with 2 or 6. (That's just one example, there are loads more, probably infinitely many.) --Tango (talk) 02:38, 13 February 2011 (UTC)

But what if d is really really large compared with k, like what if I know the first fifty decimal places? And if the answer is negative, then does that mean that for any given k and d, I can find another positive integer j, different from k, with the first d decimal places after the decimal point being identical to that of k? How can that be proven? How can such a j be constructed?174.29.78.245 (talk) 02:43, 13 February 2011 (UTC)

For any d and a, there are infinitely many k giving rise to them. This can be proved from the fact that ${\sqrt {n+1}}-{\sqrt {n}}$ converges to 0. Algebraist 02:46, 13 February 2011 (UTC)

More concretely, you can set j to either of $10^{2d}+2a+1$ or $10^{2d}+2a+2$ because $(10^{d}+10^{-d}a)^{2}=10^{2d}+2a+(10^{-d}a)^{2}$ and the last term is less than 1. –Henning Makholm (talk) 03:23, 13 February 2011 (UTC)

None of these responses fall under the assumption that k is small compared to d. Perhaps a better way to pose the question: Given 0≤a<b≤1, find the smallest integer k so that the fractional part of √k is between a and b.--RDBury (talk) 06:37, 13 February 2011 (UTC)

You can loop to find the smallest k that satisfies your inequalities, but I suppose that you're looking for a number theoretic algorithm that runs in time poly(log(k)). Let $f=(a+0.5)/10^{d}$ be your approximation to the fractional part of ${\sqrt {k}}$. Use continued fractions to find an approximation $f\approx p/q$ where q is "not too small and not too big". Let $b=round(f^{2}q)$. Solve $2xp=-b$ (mod q) for x (choose the smallest x if there are multiple solutions). Then $k=round((x+f)^{2})$.

For example, f = 0.4721355 ≈ 754/1597 = p/q. 0.4721355^2*1597 ≈ 355.99035, so b = 356. Solve 2*x*754 = -356 (mod 1597) to get x = 4. (4 + 0.4721355)^2 ≈ 19.99999593, so k = 20. 98.248.42.252 (talk) 07:21, 13 February 2011 (UTC)

I can see what you're trying to do there, but the roundings feel rather ad-hoc. Can you prove that this procedure works? What if q is even and b is odd -- then there is no solution for x. –Henning Makholm (talk) 15:04, 13 February 2011 (UTC)

To take a slightly different approach, the problem can be reduced to a more general, but linear problem: given two lines, y=ax+b and y=cx+d, where a<c, find the left most integer point (h, k) in the region above the first line and below the second line. Stated this way it's a problem integer programming with two variables and two constraints.--RDBury (talk) 08:04, 13 February 2011 (UTC)

If you assume the digits are random numbers this reduces to the birthday problem. You'd need d to be about twice the number of digits in k or more to have a good chance of not having a clash in the numbers from 1 to k. The numbers would be spread fairly evenly which would lower the chances of a clash but I doubt it would be much less than that. Dmcq (talk) 09:47, 13 February 2011 (UTC)

Efficient linear algebra in a world of partial knowledge

I have to solve a large number of matrix equations of the general form:

$A_{i}\,X_{i}=B_{i}$

Where the matrix $A_{i}$ is square, symmetric, everywhere non-negative, full rank, and ~90% sparse.

Further, the i-th step and the (i+1)-th step have most of their entries in common. After permuting rows and columns as necessary, one can expand $A_{i}$ and $A_{i+1}$ in terms of submatrices such that:

${\begin{bmatrix}A_{i,a}&A_{i,b}\\A_{i,b}^{T}&A_{i,d}\end{bmatrix}}{\begin{bmatrix}X_{i,1}\\X_{i,2}\end{bmatrix}}={\begin{bmatrix}B_{i,1}\\B_{i,2}\end{bmatrix}}$ and ${\begin{bmatrix}A_{i+1,a}&A_{i+1,b}\\A_{i+1,b}^{T}&A_{i+1,d}\end{bmatrix}}{\begin{bmatrix}X_{i+1,1}\\X_{i+1,2}\end{bmatrix}}={\begin{bmatrix}B_{i+1,1}\\B_{i+1,2}\end{bmatrix}}$

where $A_{i,a}=A_{i+1,a}$, $B_{i,1}=B_{i+1,1}$, and $A_{i,a}$ is square and contains approximately 90% of the entries in $A_{i}$.

Intuitively, it seems like solving the i-th problem should help one solve the (i+1)-th problem, after all most of the entries overlap. I can show that if $A_{i,a}^{-1}$ is already known, then both the i-th and (i+1)-th problem can be solved quickly. The difficulty arises that the common submatrix between i-th and (i+1)-th is not the same as the one between the (i+1)-th and (i+2)-th step, etc. So doing that inverse for the i and i+1 steps doesn't help on later steps.

Ideally, I'd like to find a general process that I can use which would allow me to always take the prior result and have it help in the computation of the next step. I need to solve thousands of such matrix equations where $A_{i}$ typically has tens of thousands of rows. This is expected to take many hours, and I would like to find ways to speed it up by exploiting the known relationship between adjacent steps. Is there a good way to express the relationship between the i-th and (i+1)-th step?

In the alternative, is there any way to exploit the properties of $A_{i}$ described in the opening to speed up the general process? Dragons flight (talk) 08:00, 13 February 2011 (UTC)

Finitely presented groups isomorphic

Hi there,

I'm trying to show the finitely presented groups G=<$a,b|a^{3}=b^{2}$> and H=<$x,y|xyx=yxy$> are isomorphic. I've noticed that in H, $(xy)^{3}=(yxy)^{2}$, but if I define the map f by f(a)=xy, f(b)=yxy, then I'm not sure whether this is a well-defined isomorphism, or indeed how to show it. We can get f(s)=x and f(t)=y for some x,y, so it's certainly surjective, but I can't clearly see how to show it's injective - and can we just 'define' "f(product of 'a','b') = product of f(a),f(b)" to get the homomorphism property? I'm not sure how to show that that's well-defined, other than noting that f($a^{3}b^{-2}$)=$e_{H}$=f($e_{G}$), but does that suffice?

Thankyou for any insight! 131.111.185.74 (talk) 20:02, 13 February 2011 (UTC)

Yes, that suffices to show welldefinedness of the homomorphism. By the universal property of free groups, there's a unique homomorphism f from <a,b> to H given by f(a)=xy, f(b)=yxy. Since this map sends a³b⁻², to the identity, it induces a welldefined homomorphism from the quotient group <$a,b|a^{3}=b^{2}$> to H by the universal property of quotients. By the same argument, there's a unique homomorphism g from H to G given by g(x)=a²b⁻¹, g(y)=ba⁻¹. gf is then a homomorphism from G to G which satisfies gf(a)=a, gf(b)=b, hence gf is the identity and so g and f are inverse isomorphisms. Algebraist 21:13, 13 February 2011 (UTC)

(strange time-delayed edit non-conflict). Here is essentially what Algebraist said, with more details (more because I've written it anyway than because it really needs more pounding). First let me reexpress what you have already done in terms of free groups and quotients:

1. G and H are quotients, $G=F_{ab}/\langle a^{3}b^{-2}\rangle$ and $H=F_{xy}/\langle xyx(yxy)^{-1}\rangle$ where $F_{ab}$ is the free group over {a,b} and $\langle {\cdot }\rangle$ is the normal closure.
2. You now define a homomorphism $\phi :F_{ab}\to F_{xy}$: $\phi (a)=xy$ and $\phi (b)=yxy$.
3. By direct computation, $\phi (a^{3}b^{-2})\in \langle xyx(yxy)^{-1}\rangle$.
4. You have also found some $\psi (x)$ and $\psi (y)$ such that $\phi \circ \psi$ is the identity on $F_{xy}$. Therefore, $\phi$ is surjective.
5. (Your $f:G\to H$ now arises by composing $\phi$ with the canonical projection $\pi _{H}:F_{xy}\to H$ and factoring $\pi _{H}\circ \phi$ through the projection $\pi _{G}:F_{ab}\to G$. Since $\phi$ and $\pi _{H}$ are both surjective, so is $f$.)

Now you actually lack very little:

1. Show that $\psi \circ \phi$ is the identity on $F_{ab}$. Thus, $\phi$ is injective so an isomorphism.
2. Show that $\psi (xyx(yxy)^{-1})\in \langle a^{3}b^{-2}\rangle$, so the two kernels are isomorphically related by $\phi$.
3. Then, immediately, the quotients must also be isomorphic. (In terms of $f$, the critical fact is that the kernel of $\pi _{H}\circ \phi$ is $\langle a^{3}b^{-2}\rangle$, so $f$ becomes an injection by the first isomorphism theorem).

–Henning Makholm (talk) 22:22, 13 February 2011 (UTC)

Great circle direction

I traverse the earth (assume a perfect sphere), starting, say, at the Royal Observatory, Greenwich heading north west, a bearing wrt N of 315.5 degrees, and I stay on that great circle. Is there a simple formula for the bearing as a function of longitude? -- SGBailey (talk) 20:49, 13 February 2011 (UTC)

It's easier to solve the problem at first if we start off at the equator (a general formula then follows from this special case). Suppose we start at the equator, traveling along a great circle that makes an initial angle of α₀ with the equator. Let k be the unit normal vector to the equatorial plane and n the unit vector normal to the plane containing the great circle of motion. The angle between n and the latitudinal plane remains constant, and so the sine of the angle of the path taken with a line of latitude is

$\sin \alpha =(\mathbf {k} \times \mathbf {n} )\cdot \mathbf {N}$

where N is the unit normal to the sphere. The vector N depends on the point of the path, and there does not seem to be a simple formula for it that depends only on the longitude. One can obtain explicit formulas using Euler angles, but it seems to get slightly messy. In the end, after an unpleasant grind, I get

$\sin \alpha ={\frac {\cos \alpha _{0}\sin \alpha _{0}}{\sqrt {\cos ^{2}\alpha _{0}+\tan ^{2}\phi }}}$

where φ is the longitude. I'm not sure how reliable I would consider this formula though, unless it was reproduced independently. Sławomir Biały (talk) 22:33, 13 February 2011 (UTC)

It is easier to use the dual spherical law of cosines on the right triangle formed by the great circle, the equator and the meridian through the moving point. One of the terms drops out due to the right angle and I get simply:

$\sin \alpha =\cos(\pi /2-\alpha )=\sin \alpha _{0}\cos \phi$

where as in your formula $\alpha$ is the angle between the bearing and due east. The actual compass bearing is $\cos ^{-1}(\sin \alpha _{0}\cos \phi )$. –Henning Makholm (talk) 22:58, 13 February 2011 (UTC)

That's a clearer approach. I was also ultimately able to reproduce this value in my own awkward way. Sławomir Biały (talk) 23:50, 13 February 2011 (UTC)

Thanks guys. -- SGBailey (talk) 23:11, 13 February 2011 (UTC)