Mathematics desk
< August 23	<< Jul \| August \| Sep >>	August 25 >

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 24

Symmetry groups

The article Symmetry group states that that all finite discrete symmetry groups are "finite point groups, which include only rotations, reflections, inversion and rotoinversion". Is this true? I may be missing something obvious but it is not immediately apparent to me that, for example, all graph automorphisms can be represented in terms of these operations. — Preceding unsigned comment added by 109.144.190.19 (talk) 11:48, 24 August 2013 (UTC)[reply]

A symmetry group by definition consists of isometries: maps that preserve distances (in the geometric sense). Graphs, and hence graph automorphisms, do not have a natural distance function associated with them as an embedding in a metric space (in which distances can be defined), and as such do not seem to be candidates for the concept of a symmetry group. It would seem obvious to me, in the specific case of a Euclidean space, that this holds: translation symmetries form infinite symmetry groups, and the composition of any pair of Euclidean symmetries that do not preserve the same point necessarily generate an infinite group. This statement does not hold in elliptic geometries, but the article does limit itself to Euclidean geometries. — Quondum 13:43, 24 August 2013 (UTC)[reply]

I agree that it is obvious that all finite groups of operations on euclidean space do not include translation. What does one call the group whose elements correspond to the automorphisms of a given graph? — Preceding unsigned comment added by 31.55.76.152 (talk) 22:04, 24 August 2013 (UTC)[reply]

The automorphism group of a graph. See Graph automorphism for details. --Mark viking (talk) 22:21, 24 August 2013 (UTC)[reply]

This is a longish answer, so bear with me. The article you linked to is primarily focused on symmetries of Euclidean Space, thus the limitations. However, there is a deep, and fairly fundamental (see Symmetry in mathematics), interaction between groups and geometries. To that end, you may be interested in looking at Finite geometry, our article Fano plane gives an example with some relations to symmetry. For some more examples: our article Projective plane discusses the finite case at various points (as well as some of its symmetry), related to this, you may be interested in Wedderburn's little theorem; spinning off from there, Wedderburn's theorem is generalized by the Artin–Zorn theorem, which is related to Moufang planes- which, in turn, are related to symmetries and projective planes (The theorem shows that every finite Moufang plane is a Desarguesian plane, in contrast to a Non-Desarguesian plane, which again has a relation finite groups)- you may also want to read Projective transformation, Homography, and Collineation. Also relating to finite geometry and its symmetries, check out Steiner system and Mathieu group. Going in a slightly different direction, Klein started the Erlangen program to use groups to discuss geometry, in this regard, you may be interested in Homogeneous space, Group action, and Lie group- you may also be interested in Klein geometry. In that vein, but more advanced, you may also have an interest in the structure group section in our article Fiber bundle, and the articles Vector bundle, Principal bundle Connection (principal bundle); another connection (ha!) between groups and geometric structure can be found at Homology (mathematics), Homology theory, Simplicial homology- and, staying with topology, Homotopy and Homotopy group, which are more difficult to work with, but fairly intuitive conceptually. And, since graphs relate to the topological theories mentioned, we've come full circle; and I would recommend, Algebraic graph theory and Frucht's theorem which says that every finite group is the group of symmetries of a finite undirected graph. Finally, for real this time, you may also be interested in Geometric group theory, and the less related Classification of finite simple groups which is related to the Mathieu and Lie groups (finite cases), and (related to finite geom.) Galois geometry. I apologize for not providing detail on any of the subjects mentioned, but this would have made this post unwieldy in size; and our articles, as well as google, give a lot of detail on these matters.Phoenixia1177 (talk) 06:45, 25 August 2013 (UTC)[reply]

You should also consider Cayley graph, related to Cayley's theorem, for another intersection of graphs and groups.Phoenixia1177 (talk) 08:19, 25 August 2013 (UTC)[reply]

Thanks very much Phoenixia, I appreciate the suggestions and guidance. — Preceding unsigned comment added by 109.144.132.49 (talk) 19:00, 25 August 2013 (UTC)[reply]

No problem; and thank you for the thank you:-) Symmetry is one of those beautiful underpinnings of mathematics, it's lurking beneath, around, above, and between every theorem (mostly). Indeed, just as you can recast most of mathematics in terms of set theory, you can do the same thing with Category theory, which, essentially, focuses on the maps between mathematical objects (in most common areas, these maps are symmetries of some form). I'm not exactly sure what your interests are- symmetry, groups, or graphs- but if I can be of any further assistance, please let me know:-)Phoenixia1177 (talk) 19:44, 25 August 2013 (UTC)[reply]

Rational solutions of x^y = y^x

The above thread #Intersection of two "curves". gives rise to this question: We know from the graphical arguments in that section that $x^{y}=y^{x}$ with x < y has only one integer solution, namely (2, 4). But how many rational solutions does it have? I'm guessing either only one or an infinitude of them, but if it's the latter then how do you find them? Duoduoduo (talk) 15:59, 24 August 2013 (UTC)[reply]

Let x=(1+1/n)ⁿ, y=(1+1/n)ⁿ⁺¹ where n is any positive integer. (n=1 gives the x=2, y=4 solution.) A quick calculation shows x^y=y^x for all n. This may not include all solutions but it shows there are an infinite number. --RDBury (talk) 16:18, 24 August 2013 (UTC)[reply]

For n=2, the solution is x=(1 1/2)^2 = 2 1/4 and y=(1 1/2)^3 = 3 3/8. For any real values x and y, the values will be closer the closer they are to 271801/99990. (This is not affected by whether the values are rational or irrational.) Georgia guy (talk) 17:08, 24 August 2013 (UTC)[reply]

Right, RDBury's formula for x is increasing in n (and y is decreasing in n). This raises the question: is the smallest possible rational value for x that solves

x^{y}=y^{x}

equal to 2? Duoduoduo (talk) 17:53, 24 August 2013 (UTC)[reply]

Is 0^0 defined? If so, then that's definiely the smallest! Also, since x and y are interchangeable, and y can be less than 2 (the limit is y=1), then x can also. I wonder if there is a solution in 0<x<1 ? MChesterMC (talk) 09:19, 27 August 2013 (UTC)[reply]

Yes,

0^{0}

is defined to equal 1 (see Exponentiation#Zero to the power of zero). My question about a rational solution with x<2 implicitly referred to the case x<y, which precludes

0^{0}=0^{0}

, as well as cases like

{\tfrac {1}{100}}^{\tfrac {1}{100}}={\tfrac {1}{100}}^{\tfrac {1}{100}}

. Duoduoduo (talk) 12:36, 27 August 2013 (UTC)[reply]

Actually the article that you link explains that there is a variety of views on the question of whether it is appropriate to define 0⁰ to be 1. As a general rule, this definition is harmless (and useful) in contexts where the exponent 0 is interpreted as a natural number, but the situation is much less clear when it is interpreted as a real or complex number. --Trovatore (talk) 23:55, 27 August 2013 (UTC)[reply]

Sorry, I should have said it's very usually defined that way in the present non-continuous context of integers. Anyway, my point was that the answer to his question of whether it is defined, is yes. Duoduoduo (talk) 13:30, 28 August 2013 (UTC)[reply]

How is that the "present context"? It appears to me that the "present context" is real-to-real exponentiation. That's normally defined by

x^{y}=\exp(y\log x)

, and its domain is

x>0\,\!

. So the answer to his question, in this context, is "no". --Trovatore (talk) 18:44, 28 August 2013 (UTC)[reply]

The present context is given by the question asked by the OP (that would be me): how many rational solutions does it have? Duoduoduo (talk) 19:50, 28 August 2013 (UTC)[reply]

Yes, the smallest possible value for nonnegative rational x ≠ y is 2, and in fact, RDBury’s formula gives all rational solutions. Write x = a/b and y = c/d with gcd(a,b) = gcd(c,d) = 1. The assumption x^y = y^x translates to a^bcd^ad = b^bcc^ad, which in view of the coprimality conditions implies a^bc = c^ad and b^bc = d^ad. The former implies that a = uⁿ and c = u^m for some integer u and coprime positive n, m, namely n = ad/gcd(ad,bc) and m = bc/gcd(ad,bc), and likewise b = vⁿ, d = v^m for some v. Since gcd(a,b) = 1, we must have gcd(u,v) = 1. Also, x ≠ y implies u ≠ v and n ≠ m. We have

n={\frac {ad}{\gcd(ad,bc)}}={\frac {a}{\gcd(a,c)}}{\frac {d}{\gcd(b,d)}}={\begin{cases}u^{n-m}&n>m,\\v^{m-n}&n<m,\end{cases}}

and likewise

m={\begin{cases}v^{n-m}&n>m,\\u^{m-n}&n<m.\end{cases}}

Assuming x < y, this is easily seen to imply u > v and n < m, whence n = v^{m − n}, and

m=u^{m-n}=(v+(u-v))^{m-n}=v^{m-n}+(m-n)(u-v)v^{m-n-1}+\underbrace {{\binom {m-n}{2}}(u-v)^{2}v^{m-n-2}+\cdots } _{{\text{if }}m-n>1},

thus

1=(u-v)v^{m-n-1}+\underbrace {{\frac {m-n-1}{2}}(u-v)^{2}v^{m-n-2}+\cdots } _{{\text{if }}m-n>1}.

Since the first term on the RHS is a positive integer and the other terms are positive, this is only possible if m = n + 1 and u = v + 1, which implies n = v and m = u. Thus, x = (u/v)ⁿ = (1 + 1/n)ⁿ and y = (u/v)^m = (1 + 1/n)ⁿ⁺¹.—Emil J. 17:46, 29 August 2013 (UTC)[reply]

Fantastic! Thanks. Duoduoduo (talk) 21:58, 29 August 2013 (UTC)[reply]

It looks to me (correct me if I'm wrong) that the formula x=(1+1/n)ⁿ, y=(1+1/n)ⁿ⁺¹ gives all real solutions of x^y = y^x, rational or irrational, if n is allowed to range over the positive reals. The formulas for x>1 and y>1 are both monotonic in n>0. So for any real value of x>1 there is a unique real value of n, and associated with this x value there is a unique value of y by the graphical argument given in an earlier thread that since (log z)/z is quasi-concave the solutions of x^y = y^x are given by finding the two intersections of (log z)/z with any horizontal line. This unique y value is indeed found by y=(1+1/n)ⁿ⁺¹ since it satisfies the desired equation x^y = y^x.

From this we have that y/x = 1 + 1/n. So when x and y are irrational the ratio y/x can be either irrational (when n is irrational) or rational (when n is rational but non-integer). The ratio can even equal an integer, when n has the form 1/k. Duoduoduo (talk) 13:50, 30 August 2013 (UTC)[reply]

Finding the root of a vector fixed point function

I need to find the root of a fixed point function g(x)=x-f(x) with x a vector up to ~100 dimensional. The function exaluation is very computationally expensive relative to any operators on x, and efficiency is important. For this reason a numerical derivative is practically out of the question. An analytical derivative is not available. I've implemented Broyden's method and it works most of the time and fails occassionally for what looks like round-off reasons - for example changing a function to another equivalent function can cause the convergence to fail or succeed. Is there a method for stabilising Broyden's method? I've looked into DIIS but I can't figure out what error vector makes sense in a fixed point calculation. As far as I can see, most research is in optimisation on scalar f(x). I tried BFGS with numerical derivative and Nelder-Mead on |g(x)|, but of course it's very innefficient. Can you suggest an approach or appropriate method? Thanks for your assistance, Doug (talk) 20:07, 24 August 2013 (UTC)[reply]

Regarding the round-off error, are you using the maximum precision variables allowed in your computer language ? If so, then there are some languages which allow for arbitrary-precision arithmetic, perhaps you might want to try one of those. StuRat (talk) 02:23, 25 August 2013 (UTC)[reply]