Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Galois Groups for a system of Linear equations?

  1. Jan 7, 2012 #1
    If I were to solve a system of multiple equations in the form
    αx+βy+ζz=p[itex]_{1}[/itex]
    Where α,β,ζ are constants x,y,z are variables, and p is a prime, how would I use Galois theory and/or number theory to find the number of solutions if the other equations could all be written in the form

    α[itex]_{i}[/itex]x[itex]_{i}[/itex]+β[itex]_{i}[/itex]y[itex]_{i}[/itex]+ζ[itex]_{i}[/itex]z[itex]_{i}[/itex]=p[itex]_{i}[/itex] where, once again, each α,β,ζ are constants, each p is a distinct prime, and x,y,z are all variables?

    Thanks in advance.
     
  2. jcsd
  3. Jan 8, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    You should clarify two points.

    1. Are you dealing with an applied math situation where the coefficients of your equation are approximate values, such as measured temperatures etc. I don't think Galois theory (at least as it is currently practiced) is useful in such a situation. It depends on exact numerical relations.

    2. Is your main interest in solving a particular problem or are you simply trying to understand Galois theory? (I won't be of much help in the latter case!)
     
  4. Jan 8, 2012 #3
    Thanks for asking for clarification, I didn't think my question was very clear.

    First off, I am not dealing with an applied problem or any particular problem with approximate coefficients. Secondly, I want to know how to use Galois Theory and/or Number Theory to solve a particular class of problems (namely linear systems of 2 or 3 variables where the sum of each variable multiplied by a certain coefficient equals a prime). I am not concerned with what the solutions are, but I though since the type of problem lends itself to number theory and permutation groups, that Galois Theory would help determine the number of solutions.
     
  5. Jan 8, 2012 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    The topics of primes and number theory suggest that you might be interested in the integer solutions to such equations. Is that the case? Or are you trying to count the number of solutions that involve any real numbers?
     
  6. Jan 8, 2012 #5
    Yes, of course, I should have mentioned that. I am looking for the process of solving this problem in the field [itex]\textbf{Z}[/itex]/n[itex]\textbf{Z}[/itex]. That is, I am trying to figure out how to solve this problem generally for integers less than an integer n.
     
  7. Jan 8, 2012 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    So we assume n is a prime number.

    Technically, that's not the same as solving in terms of residue classes of integers mod n, but I'll assume that's what you meant.

    The only suggestion I have is use the usual way of operating on simultaneous equations (using arithmetic mod n) to eliminate as many variables as possible, so that you end up with a single equation in one or more unknowns. I think there is a well developed theory of solving a single linear congruence in several unknowns. I don't know that theory by memory. I'd have to look it up.

    It isn't clear what kind of answer you want. Are you looking for some theorem that is more sweeping and abstract? I suggest you formulate your question precisely and post it in the forum section on number theory. (The usual application of Galois theory deals with the solution of polynomial equations in a single unknown. I'm not familiar with generalization of the idea to situations involving several variables. Any forum member who is, is welcome to chime in.)
     
  8. Jan 8, 2012 #7
    Didn't mean to imply that, the only primes are p, n just determines what solutions x such that x<n-1 we are concerned with. If you want a specific problem, say n=12.

    I did not intend to suggest that we were working with residue classes. I know that is how it could be written and is not technically the same, but I did not mean for residue classes to have any special significance. You could consider it (for n=12) to be all of the integers mod 12, which allows for extra solutions, but I am only concerned with those that are equal to or less than 11.

    I had this idea earlier, but then the equation would be in the form α[itex]_{1}[/itex]a+f=0

    Where a is a variable, α[itex]_{1}[/itex] a constant, and f is a function of the different primes. This seems to be solvable by Galois theory. I got this far but I didn't know what to do with the function f(p[itex]_{i}[/itex]). I'd like a general result but maybe I could try factoring mod c and solving for c over the primes. But then how would I factor a system mod c in the primes?

    Maybe the question would be more illustrative if I gave a numerical example of what I was trying to solve:

    3a+2b+c=p[itex]_{1}[/itex]
    2a+b+5c=p[itex]_{2}[/itex]
    3c-b=p[itex]_{3}[/itex]

    Where p[itex]_{i}[/itex] are all primes [not necessarily prime ideals] and a,b,c are less than 12. I just made up this problem to see if anyone could explain the process; I'm interested in how I would apply this process to any of the original class of problems (using Galois Theory or Abstract A.gebra), not with the actual solution.
     
    Last edited: Jan 8, 2012
  9. Jan 8, 2012 #8

    Stephen Tashi

    User Avatar
    Science Advisor


    OK, I understand your example. You have equations (=) instead of congruences ([itex] \equiv [/itex] mod n). You're seeking non-negative integer solutions for a,b,c that are each less than 12 in the example, correct?

    At the moment, I don't see how number theory adds any knowledge to the solution of the problem that isn't already present in the ordinary theory of solving simultaneous linear equations.

    If the determinant of the coefficients is not zero, the equations have a unique solution and either it meets your requirements or it doesn't.

    A more interesting case is when there are infinitely many solutions. Then they are a subset of [itex]R^3 [/itex]. What does this space look like? I suppose the usual way to write it is to let [itex] (a_0,b_0,c_0) [/itex] be one particular solution to the equations. Then each solution can be written as [itex] (a_0,b_0,c_0) + v [/itex] where [itex] v [/itex] is a solution to the homogenous equations

    3a+2b+c=0
    2a+b+5c=0
    3c-b=0

    The set of solutions looks like a vector subspace of [itex] R^3 [/itex] that has been translated away from the origin by adding the vector [itex] (a_0,b_0,c_0) [/itex] to each of its points. To get an answer that meets your requirements, you must determine if that set contains some member of a lattice of points.

    Determining the answer to that might involve some number theory, but I'm still not sure if that's the kind of thing you have in mind.

    If you were thinking about applying group theory to the problem, I assume you were thinking about permutation groups What things were you going to permute with the permutations?
     
  10. Jan 9, 2012 #9
    Yes, but you could easily introduce number theory by writing the specific cases and finding the number of solutions to the equations
    3a+2b+c=([itex] \equiv [/itex]1 mod 4)
    2a+b+5c=([itex] \equiv [/itex]1 mod 4)
    3c-b=([itex] \equiv [/itex]1 mod 4)
    3a+2b+c=([itex] \equiv [/itex]3 mod 4)
    2a+b+5c=([itex] \equiv [/itex]3 mod 4)
    3c-b=([itex] \equiv [/itex]3 mod 4)

    Which reduces to the original problem, how to find the number of solutions to a system where each equation equals a distinct prime.

    If you solved for p in a vector subspace of the prime numbers instead of the real numbers, would that accomplish anything?
    3a+2b+c-p[itex]_{1}[/itex]=0
    2a+b+5c-p[itex]_{2}[/itex]=0
    3c-b-p[itex]_{3}[/itex]=0
    You could use your idea to solve for a,b, and c over the reals and then solve for p over the primes. The only thing is I was looking for a way of determining the number of solutions without solving explicitly.

    Yes, I was thinking about permutation groups, which is why I though Galois Theory might be useful. My idea was that you could think of the problem as permuting the digits in a base m arithmetic to form a three digit prime. Where m= max(α[itex]_{i}[/itex],β[itex]_{i}[/itex],ζ[itex]_{i}[/itex]).
     
  11. Jan 9, 2012 #10

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't see the connection between those equations and the original problem. If those are 6 simultaneous equations then they have no solution.
    How do you intend to define a "vector subspace of the prime numbers"?

    Solve for p? In your exampe, are p1 and p2 are given primes or are they unknowns to be solved for along with a,b,c ?


    I have no idea what you mean by that.
     
  12. Jan 9, 2012 #11
    Sorry, a bit of a formatting issue. I meant to say:
    3a+2b+c[itex] \equiv [/itex]1 mod 4
    2a+b+5c[itex] \equiv [/itex]1 mod 4
    3c-b[itex] \equiv [/itex]1 mod 4
    3a+2b+c[itex] \equiv [/itex]3 mod 4
    2a+b+5c[itex] \equiv [/itex]3 mod 4
    3c-b[itex] \equiv [/itex]3 mod 4

    Since every prime is either congruent to 1 mod 4 or 3 mod 4 (except 2). This isn't very useful solving over the reals, but since we know the solutions need to be less than n (say 12), this might help with formulating a general class of solutions.

    Perhaps it wasn't phrased correctly but I was asking if you could use your technique of setting the RHS equal to zero and solve for solutions of p that are elements in the set of primes. Probably not going to get anywhere with this, unless there is some technique that I cannot think of for solving within a particular set. I would assume the process wouldn't be too different from ascertaining the number of solutions in another set (such as the rationals), but I may be mistaken.

    p[itex]_{i}[/itex] (i abbreviated the subscript for simplification purposes) are unknown primes. However, I am not concerned with the solutions for a,b,c,p[itex]_{1}[/itex],p[itex]_{2}[/itex],p[itex]_{3}[/itex] etc. but rather with the process of using Galois Theory/Number Theory to solve a general system in the form α[itex]_{i}[/itex]x[itex]_{i}[/itex]+β[itex]_{i}[/itex]y[itex]_{i}[/itex]+ζ[itex]_{i}[/itex]z[itex]_{i}[/itex]=p[itex]_{i}[/itex] where, once again, each α,β,ζ are constants, each p is a distinct prime, and x,y,z are all variables?




    I meant that each equation could be written as 3 digit primes where a,b,c are variables which could be permuted as digits rather than roots. For example, set λ equal to the coefficient of the variable y (set λ=β[itex]_{1}[/itex]) in the first system. Then the equation

    xλ[itex]^{2}[/itex]+yλ+z=p[itex]_{1}[/itex]

    Where λ is a constant and x,y,z are variables

    Could be written in base g=λ[itex]^{2}[/itex]+1=1+max(α[itex]_{1}[/itex],β[itex]_{1}[/itex],ζ[itex]_{1}[/itex]) as

    xyz

    With each letter now representing a digit rather than a number.

    An example is, say we are trying to solve the equation

    4x+2y+z=p[itex]_{1}[/itex]

    Then this can be expressed as xyz in base 5 where the digits xyz can be permuted, so long as they form a three digit prime in base 5. The same can work for any base g as long as
    λ[itex]^{2}[/itex]=max(α[itex]_{1}[/itex],β[itex]_{1}[/itex],ζ[itex]_{1}[/itex]) implies that λ[itex]^{2}[/itex]=α[itex]_{1}[/itex], λ=β[itex]_{1}[/itex], 1=ζ[itex]_{1}[/itex].

    I don't mean to confuse the problem here and I know I am not being consistent with my examples but I am just trying to come up with some ideas that could help find a solution.
     
  13. Jan 9, 2012 #12

    Stephen Tashi

    User Avatar
    Science Advisor

    But pairs of equations like
    3c-b[itex] \equiv [/itex]1 mod 4
    3c-b[itex] \equiv [/itex]3 mod 4
    are inconsistent with each other.

    We're need to get straight which variables are unknowns and which are given in this problem. If we set the right hand side of the equations equal to zero, what would you mean by "solutions of p" ? Aren't the primes p what makes up the right hand side of the equations?



    Is the condition that "each p is a distinct prime" a new requirement? You need to make a precise statement of the problem that you want to solve, including a statement of exactly which things in the problem are variables and which are known constants.

    I still don't understand. To me, the sequence of digits xyz in base 5 represents the number 25x + 5y + z and I don't see what that has to do with the original equation
     
  14. Jan 11, 2012 #13
    Yes, I thought the OR was implied, but I probably should have specified that since I wanted to know the number of solutions that I would account for
    3c-b[itex] \equiv [/itex]1 mod 4 Or 3c-b[itex] \equiv [/itex]3 mod 4 being true.

    The coefficients α,β,ζ are given but the variables a,b,c (or x,y,z as I used earlier) as well as the primes p are unknown. I thought that by subtracting p from each side and merging it with the term with a coefficient of 1, since this would not change the number of solutions in Galois Theory since it would then be in the form (using the base 2 example mentioned below)
    4a+2b+d=0
    Where d is a constant formed by the sum of c and p, which does not change the number of solutions.


    Pretty sure that "each p is a distinct prime" is not a new requirement since I copy pasted from an earlier post:
    I thought I made it pretty clear which were variables and which were constants, but I understand that there was some confusion about whether p was known or not and I hope I have cleared that up.

    Sorry, I meant to say base 2, my bad.

    Also, I just decided to look into something you said earlier:
    This might be on to something, using the number theory technique of writing equations that are equivalent to a prime as congruences, one could use this: https://en.wikipedia.org/wiki/Linear_congruence_theorem to determine the possible solutions.

    Wikipedia also says that: "In particular, there will be exactly d = gcd(a,n) solutions in the set of residues {0,1,2,...,n-1}," referring to the equation ax[itex]\equiv[/itex]b mod n.

    The bottom of the page explains how to solve a system of linear congruences, but this technique would only get me the number of solutions to the system of congruences in the form αx+βb+ζc[itex]\equiv[/itex]3 mod 4 or αx+βb+ζc[itex]\equiv[/itex]1 mod 4, without regard for the fact that these congruences don't necessarily define the original problem precisely (because not all numbers k such that k [itex]\equiv[/itex]3 mod 4 or k[itex]\equiv[/itex]1 mod 4 are necessarily prime numbers). This definitely helps narrow down the solutions and make some progress, but I don't know what to do from there.
     
    Last edited: Jan 11, 2012
  15. Jan 12, 2012 #14

    Stephen Tashi

    User Avatar
    Science Advisor

    A significant aspect of the permutations in the groups that arise in Galois theory is that the leave some important quantities unchanged. I don't see how your example of permuting digits of a number leaves any important quantity in the problem unchanged.

    It's probably best to analyze the specific example. That may clarify the generalities.

    Check my work, it probably needs some correction.


    3a+2b+c=p1
    2a+b+5c=p2
    3c-b=p3

    ----

    3a + 2b + c - p1 = 0
    2a + b + 5c - p2 = 0
    3c - b - p3 = 0

    ----

    6a + 4b + 2c - 2p1 = 0
    6a + 3b + 15c - 3p2 = 0
    -b + 3c - p3 = 0

    -----

    b - 13c -2p1 + 3p2 = 0
    -b + 3c - p3 = 0

    -----

    16c - 2p1 + 3p2 - p3 = 0


    ------

    So if we pick any 3 distinct primes p1,p2,p3
    then solutions for a,b,c are given by:

    c = (1/16)(2p1 - 3p2 + p3) = ((1/8)p1 - (3/16)p2 + (1/16)p3

    b = 3c - p3 = (3/16)(2p1 - 3p2 + p3) - p3 = (6/16)p1 - (9/16)p2 - (13/16)p3

    a = (1/2)( -b - 5c - p2) = (1/2)(-3c + p3 - 5c - p2) = (1/2)(-8c - p2 + p3)
    = (1/2) ( (-8)(1/16)(2p1 - 3p2 + p3 ) - p2 + p3)
    = (1/2)( (-1/2)(2p1 - 3p2 + p3) - p2 + p3
    = (1/2) (-p1 + (3/2)p2 - (1/2)p3) - p2 + p3
    = (-1/2)p1 + (3/4)p2 (-1/4)p3 - p2 + p3
    = (-1/2)p1 -(1/4)p2 + (3/4)p3

    If we require each of a,b,c to be one of the integers {1,2,3...12}, we have:

    [tex] 0 \le (1/8)p1 - (3/16)p2 + (1/16) p3 \le 12 [/tex]
    [tex] 0 \le (6/16)p1 - (9/16)p2 - (13/16)p3 \le 12 [/tex]
    [tex] 0 \le (-1/2)p1 - (1/4)p2 + (3/4)p3 \le 12 [/tex]

    So the theory of solving simultaneous linear inequalties (I assume there is such a theory) is relevant.

    The requirement that a,b,c be integers may introduce some number theory.

    For example what kind of p1,p2,p3 will make a = (-1/2)p1 - (1/4)p2 + (3/4)p3 an integer?

    4a = -2p1 - p2 + 3p3 So -2p1 - p2 + 3p3 is divisible by 4.

    We get simultaneous linear congruences

    [tex] -2p1 - p2 + 3p3 \equiv 0 (mod 4) [/tex]
    [tex] 6p1 - 9p2 - 12p3 \equiv 0 (mod 16) [/tex]
    [tex] 2p1 - 3p2 + p3 \equiv 0 (mod 16) [/tex]

    There are a limited number of possibilties for the results of things like ( p1 mod 16) since p1 is prime. It looks like an interesting combinatorial problem to try the various combinations and see which ones are feasible in those equations.
     
  16. Jan 13, 2012 #15
    I thought that since permuting the digits leaves the fact that the number is prime the same makes Galois theory relevant. I may have been wrong in hindsight...

    Not sure, but I think you made an error somewhere. Maybe at the first substitution? I got
    a = 1/10 (8p1-7p2+9p3)
    b = 1/10 (9p2-6p1-13p3)
    and c = 1/10 (3p2-2p1-p3)

    It's the same as with linear equalities, we subtract, substitute, and find that the solutions satisfy

    (1/9)*(7p2-8p1)<=p3<=(1/9)*(-8p1+7p2+120)

    Would I be correct in assuming that [tex] -2p1 - p2 + 3p3 \equiv 0 (mod 4) [/tex] has r solutions in the residue class mod 12 where r=gcd{-2p1 - p2 + 3p3,12}=gcd{-2,-1,3,12}=1? That would mean that the entire system has no more than 1 solution in the residue class mod 12. Is this reasoning effective, or even correct?
     
  17. Jan 14, 2012 #16

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't know what it means for a congruence mod 4 to have "solutions in the residue class mod 12". Can you give a numerical example of that?
     
  18. Jan 15, 2012 #17
    What I meant (and I was probably using incorrect terminology) was that the congruence has 1 solution that is less than 12.
     
  19. Jan 15, 2012 #18

    Stephen Tashi

    User Avatar
    Science Advisor

  20. Jan 16, 2012 #19
    Last edited by a moderator: May 5, 2017
  21. Jan 18, 2012 #20

    Stephen Tashi

    User Avatar
    Science Advisor

    According to Theorem 3 of the Samarandache paper, −2p1−p2+3p3≡0(mod4) has [itex] (1)(4^{2}) [/itex] solutions. To this, we are adding the condition that the p's be distinct primes. So there might be zero solutions. We'll have to work it out to see.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Galois Groups for a system of Linear equations?
  1. Galois Groups (Replies: 4)

  2. Galois group (Replies: 6)

  3. Galoi group (Replies: 4)

Loading...