O(you make baby Jesus cry)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

O(you make baby Jesus cry)

Postby Blatm » Sat Jul 23, 2011 4:52 am UTC

There is a simulation that I want to run, but because I am not very good at coding right now it runs in O(exp(exp(n))). Obviously this makes my code completely useless for anything other than very small n. Hopefully some people here will be able to help me come up with some more reasonable runtimes.

The program solves a math problem by checking every possible group element of a free group "less than a certain length" for a certain property. In not-so-mathy: my elements are "strings" (not strings in the programming sense) of a's, b's, c's, ... (n letters) and -a's, -b's, -c's, so stuff like a b -a -b c b a -b -a -c. That one I just wrote has "length 10", and also has the property I want (which I'll get to later).

The O(lol) problem comes from the fact that a) I know the length of the shortest elements that will have the property I want grows exponentially with the number of generators (letters), and b) the number of elements of length d for n generators is (2n+1)^d, so if I want to check every element that's O( n^exp(n) ) ~= O(exp(exp(n))) since log(n) won't be very big (I'm expecting to only need to look at single digit n's). The first problem, a), is just a fact of life I think. The second problem, b), is the one I want some help with. Right now I'm just nesting O(exp(n)) for loops, which is what is making baby Jesus cry, but maybe there's a way around that.

My math problem is: consider a free group [imath]G[/imath] generated by [imath]a_1[/imath], [imath]a_2[/imath], ..., [imath]a_n[/imath]. Define [imath]\phi_i[/imath]: [imath]G \rightarrow G[/imath] as [imath]\phi_i(a_i) = \phi_i(a_i^{-1}) = e[/imath] (the identity), [imath]\phi_i(a_j) = a_j[/imath] for [imath]i \neq j[/imath] (and similarly for the inverses of generators), and [imath]\phi_i(gh) = \phi_i(g) \phi_i(h)[/imath] for all [imath]g, h[/imath] in [imath]G[/imath]. For example, [imath]\phi_2(a_1 a_2 a_1 a_2^{-1}) = a_1^2[/imath]. The problem is to find elements of this group [imath]g[/imath] such that [imath]g \neq e[/imath], but for every [imath]i[/imath], [imath]\phi_i(g) = e[/imath].

Here is my code (~300 lines in c++). I don't really expect anyone to go through it, but it's here for completeness. The only thing I do to try and optimize is to force every element to start with [imath]a_1[/imath], which cuts the time by 1/(2n+1) while only omitting solutions which are the same as other solutions up to renaming generators (which I don't care about). What I'm more interested in getting from this thread is just advice on how to avoid going through every element, or general advice on avoiding exp(n) nested for loops.

If you want to run the code, the shortest solutions for 2 generators are of length 4 (program runs instantly) and the shortest solutions for 3 generators are of length 10 (program takes about 10 minutes to run on my averageish laptop). The shortest solutions for 4 generators are of length 16 I think, and on my averageish laptop that would take about 60 years to run. The syntax is ./a.out <number of generators> <max length>, so ./a.out 2 4 or ./a.out 3 10 for instance.

Any help is much appreciated.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <string.h>

using namespace std;

/*
  This program searches for solutions to an algebra problem.

  Consider a free group G generated by a_1, a_2, ..., a_n. Define phi_i: G -> G as phi_i(a_i) = phi_i(a_i^-1) = e (the identity), phi_i(a_j) = a_j for i != j (and similarly for the inverses of generators), and phi_i(gh) = phi_i(g) phi_i(h) for all g, h in G. For example, phi_2(a_1 a_2 a_1 a_2^-1) = a_1^2. The problem is to find elements of this group g such that g != e, but for every i, phi_i(g) = e.

  Throughout the program I use vector<int>s to represent these group elements. For example, the vector 1 2 1 -2 would represent a_1 a_2 a_1 a_2^-1. e is represented as 0. ("the vector 1 2 1 -2" is the vector with v[0] = 1, v[1] = 2, etc.)
*/

/******************************/
/*useful generic functions*/

/*sgn(x): 1 if x is positive, -1 if x is negative, 0 if x is 0*/
int sgn(int x)
{
  if(x > 0)
    return 1;
  if(x < 0)
    return -1;
  return 0;
}

/*prints the entries of a vector in order*/
void printvec(vector<int> &v)
{
  int counter;
  for(counter = 0; counter < v.size(); counter++)
    {
      cout << v[counter] << " ";
    }
}

/*true iff v1 and v2 are the same size and all their entries agree*/
bool vecssame(vector<int> &v1, vector<int> &v2)
{
  int counter;
  bool vecssame = true;

  if(v1.size() != v2.size())
    {
      return false;
    }

  for(counter = 0; counter < v1.size(); counter++)
    {
      if(v1[counter] != v2[counter])
   {
     vecssame = false;
   }
    }

  return vecssame;
}


/*checks if every entry of v is equal to i*/
bool allthisval(int i, vector<int> &v)
{
  int counter;
  bool allthisval = true;
  for(counter = 0; counter < v.size(); counter++)
    {
      if(v[counter] != i)
   {
     allthisval = false;
   }
    }
  return allthisval;
}

bool allthisval(bool i, vector<bool> &v)
{
  int counter;
  bool allthisval = true;
  for(counter = 0; counter < v.size(); counter++)
    {
      if(v[counter] != i)
   {
     allthisval = false;
   }
    }
  return allthisval;
}

/*******************************/
/*more specialized functions*/

/*simplifies an elt, canceling things with their inverses and omiting identities where appropriate*/
void simplify(vector<int> &v)
{
  int counter = 0;

  /*remove the identities*/
  while(counter < v.size())
    {
      if(v[counter] == 0)
   {
     v.erase(v.begin()+counter);
   }
      else
   {
     counter++;
   }
    }

  counter = 0;

  /*cancel any elements next to their inverses*/
  while(counter < ((int)v.size()-1))
    {
      if(v[counter] == -v[counter+1])
   {
     v.erase(v.begin()+counter+1);
     v.erase(v.begin()+counter);
     if(counter > 0)
       {
         counter--;
       }
   }
      else
   {
     counter++;
   }
    }
}

/*turn every instance of +/- i to 0 in an elt.*/
void phi(int i, vector<int> &v)
{
  int counter;
  for(counter = 0; counter < v.size(); counter++)
    {
      if((v[counter] == i) || (v[counter] == -i))
   {
     v[counter] = 0;
   }
    }
}

/*Used to have arbirarily many nested for loops with the same range. v is a vector of counters, and every run through the loop the last one is incremented. Counting in base b and having each digit correspond to a counter will hit every possible combination of counters (in order) for each counter in the range 0..b-1. The range I want here is -b to b so the function is changed slightly to reflect that*/
void carry(int b, vector<int> &v)
{
  int counter;
  for(counter = (int)v.size()-1; counter > 0; counter--)
    {
      if(v[counter] > b)
   {
     v[counter] = -b; //in a normal carry this would be 0
     v[counter-1]++;
   }
    }
}

/*To prevent getting a bunch of solutions which are the same up to renaming generators, I want all my solutions in "canonical form". I will say that an elt. is in canonical form if the generators and their inverses appear in order when reading from left to right (i.e. the first generator to appear is +/- 1, the second is +/- 2, etc.) and the first time each generator appears it's the generator, not the inverse.*/
void canonicalform(vector<int> &out, vector<int> &in, int numnails)
{
  int counter = 0;
  vector<bool> checked(numnails, false); //whether or not each generator has appeared in the elt. yet, reading left to right
  vector<int> inverseorder(numnails); //inverseorder[n] = i means n was the ith generator to appear in the elt. from left to right, e.g. g = 4 2 1 3 has inverseorder = 3 2 4 1
  int numchecked = 0; //number of 'true's in checked
  vector<int> canonicalform; //stores the canonical form of in
  vector<int> canonsgn(numnails); //to make sure that the first time a generator appears in the canonical form it's positive (i.e. the generator and not its inverse)

  while(numchecked < numnails)
    {
      if(!checked[abs(in[counter])])
   {
     inverseorder[abs(in[counter])] = numchecked+1;
     canonsgn[abs(in[counter])] = sgn(in[counter]);
     checked[abs(in[counter])] = true;
     numchecked++;
   }
      counter++;
    }

  for(counter = 0; counter < in.size(); counter++)
    {
      canonicalform.push_back(inverseorder[abs(in[counter])]*canonsgn[abs(in[counter])]*sgn(in[counter])); //produces what was advertised in the function description
    }

  out.swap(canonicalform); //this is essentially a return statement. Vectors can't be returned directly as far as I know.
}

/*once I have a bunch of solutions in canonical form I make a new vector of solutions which contains no duplicates*/
void weedsols(vector<vector<int> > &out, vector<vector<int> > &sols)
{
  int counter1, counter2;
  vector<vector<int> > weededsols; //sols with duplicates removed
  bool newsol; //whether or not the solution at hand is new

  for(counter1 = 0; counter1 < sols.size(); counter1++)
    {
      newsol = true;
      for(counter2 = 0; counter2 < weededsols.size(); counter2++)
   {
     if(vecssame(sols[counter1], weededsols[counter2]))
       {
         newsol = false;
       }
   }

      if(newsol)
   {
     weededsols.push_back(sols[counter1]);
   }
    }

  out.swap(weededsols); //return statement
}

/*main has 4 steps: 1) it generates every possible group elt. of length < maxsize starting with 1 (since everything will be put into canonical form anyway). 2) it simplifies the group elt. If the elt. is not trivial 3) it checks if each phi_i makes it trivial. If they do then 4) the elt. is put into canonical form and stored in a solution vector.*/
main(int argc, char** argv)
{
  if(argc != 3)
    {
      cout << "./<programname> <numnails> <maxsize>" << endl;
      return -1;
    }

  vector<int> v; //group element. 1 is a_1, 2 is a_2, 0 is e, -1 is a_1^-1, etc.
  vector<int> canonicalv; //canonical form of v
  vector<vector<int> > canonicalsolutions; //nontrivial v's with phi_i(v) = e for all i, in canonical form
  vector<vector<int> > distinctsolutions; //distinct entries in canonicalsolutions
  int numnails = atoi(argv[1]);
  int maxsize = atoi(argv[2]); //max size of v's
  vector<int> counters(maxsize-1, -numnails); //to fill the v's
  int i; //counter used in various places
  vector<int> vcopy; //Because functions can't return vectors I instead have each phi modify the vector it was given. Because I want to put v into several phi'sI make a copy and give the phi's that instead in order to keep v intact.
  vector<bool> phikills; //whether or not each phi makes v trivial. phikills[i] = true means phi_i(v) = e.
  bool isgood; //if phikills[i] = true for all i, but v is not trivial itself, i.e. v is a solution.

  while(!allthisval(numnails, counters)) //this is how the program knows where the effective for loop ends: when each counter = numnails (since each counter goes from -numnails to numnails in order)
    {
      v.clear();
      v.push_back(1); //WLOG v[0] = 1
      for(i = 0; i < counters.size(); i++)
   {
     v.push_back(counters[i]);
   }

      counters[counters.size()-1]++; //progressing through the effective for loop
      carry(numnails, counters);

      simplify(v);

      if(!v.empty()) //v.empty() is true iff v is empty
   {
     phikills.clear();

     for(i = 1; i <= numnails; i++)
       {
         vcopy = v;
         phi(i, vcopy);
         simplify(vcopy);
         if(vcopy.empty())
      {
        phikills.push_back(true);
      }
         else
      {
        phikills.push_back(false);
      }
       }

     isgood = allthisval(true, phikills);

     if(isgood)
       {
         canonicalform(canonicalv, v, numnails);
         canonicalsolutions.push_back(canonicalv);
       }
   }
    }

  weedsols(distinctsolutions, canonicalsolutions); //eliminate repeated solutions

  //print results
  cout << endl << "numnails: " << numnails << endl;
  cout << "maxsize: " << maxsize << endl << endl;
  cout << "solutions:" << endl;
  for(i = 0; i < distinctsolutions.size(); i++)
    {
      printvec(distinctsolutions[i]);
      cout << endl;
    }
  cout << endl;

  return 0;
}

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: O(you make baby Jesus cry)

Postby ++$_ » Sat Jul 23, 2011 7:57 am UTC

Because the generators always appear in pairs with their inverses, we don't need to generate every string; we only need to generate those where the elements are paired with their inverses. Call these "paired strings." Every paired string of length 2n is built up from a paired string of length 2n-2 by adding a generator and its inverse. This can be done in n(2n)(2n-1) ways, if I'm counting correctly. So things are still doubly exponential, but at least the number of strings you have to consider has been reduced by a factor of something like 2n.

Can we rule out even more strings?

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: O(you make baby Jesus cry)

Postby eta oin shrdlu » Sun Jul 24, 2011 2:58 am UTC

What exactly is the problem you're trying to solve? Are you trying to write a program to enumerate all minimum-length strings with this property, or just find (by program or other method) the minimum length, or just find some (possibly not minimum-length) strings with this property, or...?

Unless you're actually trying to do an exhaustive search, I think ++$_'s hint of trying to build up these elements recursively is probably a good one. (Do you know any elements with this property, for arbitrary n?)

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: O(you make baby Jesus cry)

Postby Blatm » Sun Jul 24, 2011 4:00 am UTC

My (optimistic) end goal is to be able to describe all elements with the property for arbitrary n. The program was written to give me some example solutions so that I might get inspired. For the program to be useful I think it should produce a lot of solutions so that finding patterns is easier, but what this means is fairly arbitrary. A good start I think would be to produce all minimum length solutions. Unfortunately I don't know what the minimum lengths are, but I do know that [imath][[...[a_1,a_2], a_3]...][/imath] is always a solution, where [imath][a,b] = aba^{-1}b^{-1}[/imath], the commutator (which has length proportional to [imath]2^n[/imath], satisfying [imath]L_n = 2L_{n-1} + 2[/imath]). This is not always the shortest solution however: for 4 generators [imath][[a_1,a_2],[a_3,a_4]][/imath] is shorter than the above solution (lengths 22 vs. 16).

++$_, thank you for the suggestion. I'll try implementing conditions that require that a) every element have paired generator/generator inverses as you suggest, and b) at least one of every generator, which is another way to rule out strings, despite not being terribly effective. The hope is that these changes will let me get a solution for n = 4, length 16, but don't know if it'll be enough. I'd have to cut the runtime by a factor of 10^5 or so to get an answer in an hour.

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Wed Aug 03, 2011 12:34 am UTC

A lot of your functions iterate through the entire array, instead of breaking out when they find something invalid. If you're new to C++, check out the break keyword. That should make these functions take half as long or better (carry should only end up check two options unless counter[v.size()-1]==b for example)

Code: Select all

void carry(int b, vector<int> &v) {
   for(int counter = (int)v.size()-1; counter > 0; counter--) {
      if(v[counter] > b) {
         v[counter] = -b; //in a normal carry this would be 0
         v[counter-1]++;
      } else
         break;
   }
}

After studying your explanation for the math for half an hour I finally remembered enough of set theory to guess at some of what you meant. (The e itentity you wanted is epsilon [imath]\epsilon[/imath]?) Either I still misunderstand, or you've made some mistakes, because it looks like the equation [imath]\phi[/imath] sometimes returns sets ([imath]\epsilon[/imath]) and sometimes elements of [imath]G[/imath] which I assume are numbers, since you appear to me multiplying them. It looks more like you want [imath]\phi_i(a_i)=\phi_i(a_i^{-1})=1[/imath], [imath]\phi_i(a_j)=a_j[/imath], and you want [imath]\phi_i(g)=1[/imath]. You also don't explain where the sample equation comes from, or why it can have a [imath]a_2^{-1}[/imath] in it.
Come to think of it, I must still misunderstand something, because the shortest solution would always be [imath]a_1,a_1^{-1},a_2,a_2^{-1},a_3,a_3^{-1},...a_n,a_n^{-1}[/imath].

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Wed Aug 03, 2011 9:43 pm UTC

I think I got the idea now, from the examples. (ASSUMPTIONS:) The only option is [A B -A -B] where A/B are elements or other options. Function F is going to take a set S of numbers, and return a set. Recursive sets are unpacked so the result contains a series of elements, no subsets. Function L will take a set S and return the number of elements in F(S). I'm also going to use I(S) to count the number of elements in S
F(A) = {A} L(A) = 1
F(AB) = {AB-A-B} L(A,B) = 2*L(A) + 2*L(B) = 4
F(ABC) = {F(AB) C F(-A-B) -C} L(ABC) = 2*L(AB) + 2*L(C) = 10
F(ABCD) = {F(AB) F(CD) F(-A-B) F(-C-D)} L(ABCD) = 2*L(AB) + 2*L(CD) = 16
F(ABCDE) = {F(ABC) F(DE) F(-A-B-C) F(-D-E)} L(ABCDE) = 2*L(ABC) + 2*L(DE) = 24
F(ABCDEF) = {F(ABC) F(DEF) F(-A-B-C) F(-D-E-F)} L(ABCDEF) = 2*L(ABC) + 2*L(DEF) = 40
*I note that this is the same length as {F(ABCD) F(EF)}, but it doesn't appear to be a pattern.
F(ABCDEFG) = {F(ABCD) F(EFG) F(-A-B-C-D) F(-E-F-G)} L(ABCDEFG) = 2*L(ABCD) + 2*L(EFF) = 52
F(ABCDEFGH) = {F(ABCD) F(EFGH) F(-A-B-C-D) F(-E-F-G-H)} L(ABCDEFGH) = 2*L(ABCD) + 2*L(EFFH) = 64
* I can't help but notice that when I(S) is a power of 2, L(S) = I(S)^2, but can't deduce anything from this.
If my assumption is correct (unproven), and this is indeed shortest (provable given the assumption), this is trivial to generate recursively.

Code: Select all

int L(int vectorLength) {
    static std::vector<int> dynamic(1, 1);
   if ((int)dynamic.size() < vectorLength)
      dynamic.resize(vectorLength, 0);
    if (dynamic[vectorLength-1]==0) {
        int higher = L(vectorLength/2+(vectorLength%2));
        int lower = L(vectorLength/2);
        dynamic[vectorLength-1] = 2*higher + 2*lower;
    }
    return dynamic[vectorLength-1];
}
void FHelp(int neg,
        std::vector<int>::const_iterator &begelems,
        std::vector<int>::const_iterator &endelems,
        std::vector<int>::iterator &out) {
    int count = endelems - begelems;
    if (count == 1) {
        *(out++) = neg * (*begelems);
    } else {
        FHelp(neg, begelems, begelems+count/2, out);
        FHelp(neg, begelems+count/2, endelems, out);
        FHelp(-neg, begelems, begelems+count/2, out);
        FHelp(-neg, begelems+count/2, endelems, out);
    }
}
void F(const std::vector<int> &elements, std::vector<int> &out) {
    out.clear();
    out.resize(L(elements.size()));
    FHelp(1, elements.begin(), elements.end(), out.begin());
}

The F function should generate a variant of the shortest length with O(nlog(n)) function calls, but only touches elements O(n) times. I should note that passing a out vector by reference is fast, but not the "correct object oriented C++ approach". The correct way is to return a vector. (Yes, you can do that). If you're confused by the recursive nature, L uses dynamic algorithms, F uses divide and conquer, the difference being that F doesn't remember past results.

[Edit] I corrected the code, I generated the shortest "strings" for numbers of elements between 2 and 1000 in 7.734 seconds on my machine.[/edit]

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Thu Aug 04, 2011 6:13 pm UTC

I wrote a function to generate the all "strings" that can be generated by the commutator. So it misses all non-commutator rotations. Generating 59610 solutions for 12 elements took 5s. Unfortunately, although the times are small, RAM usage is not. 14 elements surpassed the 2GB limit in windows, and crashed. In the "spoiler" are the first few results, counts, and times for up to 14 elements.
Spoiler:
Elements (time) : numSolutions
2 (0s) : 1 solution
3 (0s) : 3 solutions
4 (0s) : 5 solutions
5 (0:00) : 14 solutions
6 (0:00) : 42 solutions
7 (0:00) : 134 solutions
8 (0:00) : 429 solutions
9 (0:00) : 1458 solutions
10 (0:00) : 4902 solutions
11 (0:00) : 17172 solutions
12 (0:03) : 59610 solutions
13 (0:18) : 213206 solutions
14 (EXCEPTION: bad_alloc)

Code: Select all

#include <vector>
#include <deque>
#include <iostream>
#include <ctime>

struct Node {
   std::vector<int>::const_iterator beg;
   std::vector<int>::const_iterator end;
   const Node *left;
   const Node *right;
   const Node *Next;

   void Generate(std::vector<int> &result, int neg=1) const {
      if (left) {
         if (neg==1) {
            left->Generate(result, neg);
            right->Generate(result, neg);
            left->Generate(result, -neg);
            right->Generate(result, -neg);
         } else {
            right->Generate(result, -neg);
            left->Generate(result, -neg);
            right->Generate(result, neg);
            left->Generate(result, neg);
         }
      } else
         result.push_back((*beg) * neg);
   }
   void Display(int neg=1) const {
      if (left) {
         if (neg==1) {
            left->Display(neg);
            right->Display(neg);
            left->Display(-neg);
            right->Display(-neg);
         } else {
            right->Display(-neg);
            left->Display(-neg);
            right->Display(neg);
            left->Display(neg);
         }
      } else {
         if (neg < 0)
            std::cout << '-';
         else
            std::cout << '+';
         std::cout << char('A'+(*beg)-1);
      }
   }
};

std::deque<std::vector<int>> GenAll(const std::vector<int> &Elements) {
   std::deque<std::vector<int>> result;
   std::vector<std::deque<Node*>> begs(Elements.size()+1);
   std::vector<std::deque<Node*>> ends(Elements.size()+1);
   std::deque<Node*> preResult;
   Node *lastNode = nullptr;
   const Node *thisNode = nullptr;
   for(std::vector<int>::const_iterator iter = Elements.begin(); iter != Elements.end(); ++iter) {
      Node *newNode = new Node();
      newNode->beg = iter;
      newNode->end = iter+1;
      newNode->left = nullptr;
      newNode->right = nullptr;
      newNode->Next = nullptr;
      begs[iter-Elements.begin()].push_back(newNode);
      ends[iter-Elements.begin()+1].push_back(newNode);
      if (lastNode)
         lastNode->Next = newNode;
      else
         thisNode = newNode;
      lastNode = newNode;
   }
   //append
   while (thisNode) {
      std::vector<std::deque<Node*>>::const_iterator thisBegs = ends.begin() + (thisNode->beg - Elements.begin());
      for(unsigned int i=0; i<thisBegs->size(); ++i) {
         Node *left = (*thisBegs)[i];
         if ((left->end - left->beg) < (thisNode->end - thisNode->beg)) { //no duplicate results
            Node *newNode = new Node();
            newNode->beg = left->beg;
            newNode->end = thisNode->end;
            newNode->left = left;
            newNode->right = thisNode;
            newNode->Next = nullptr;
            if (newNode->beg != Elements.begin() || newNode->end != Elements.end()) {
               begs[newNode->beg-Elements.begin()].push_back(newNode);
               ends[newNode->end-Elements.begin()].push_back(newNode);
               lastNode->Next = newNode;
               lastNode = newNode;
            } else {
               preResult.push_back(newNode);
            }
         }
      }
      std::vector<std::deque<Node*>>::const_iterator thisEnds = begs.begin() + (thisNode->end - Elements.begin());
      for(unsigned int i=0; i<thisEnds->size(); ++i) {
         Node *right = (*thisEnds)[i];
         Node *newNode = new Node();
         newNode->beg = thisNode->beg;
         newNode->end = right->end;
         newNode->left = thisNode;
         newNode->right = right;
         newNode->Next = nullptr;
         if (newNode->beg != Elements.begin() || newNode->end != Elements.end()) {
            begs[newNode->beg-Elements.begin()].push_back(newNode);
            ends[newNode->end-Elements.begin()].push_back(newNode);
            lastNode->Next = newNode;
            lastNode = newNode;
         } else {
            preResult.push_back(newNode);
         }
      }
      thisNode = thisNode->Next;
   }
   for(std::deque<Node*>::const_iterator iter = preResult.begin(); iter != preResult.end(); ++iter) {
      result.push_back(std::vector<int>());
      (*iter)->Generate(result[result.size()-1]);
   }
   //delete everything
   for(std::vector<std::deque<Node*>>::const_iterator oiter = begs.begin(); oiter != begs.end(); ++oiter) {
      for(std::deque<Node*>::const_iterator iiter = oiter->begin(); iiter != oiter->end(); ++iiter)
         delete *iiter;
   }
   for(std::deque<Node*>::const_iterator iter = preResult.begin(); iter != preResult.end(); ++iter)
      delete *iter;
   return result;
}

int __cdecl main(int argc, char *argv[]) {
   if(argc < 2) {
      std::cout << "required parameter <numnails>" << std::endl;
      return -1;
   }
   int maxnails = atoi(argv[1]);
   for(int numnails=2; numnails<maxnails; ++numnails) {
      clock_t start = clock();
      std::vector<int> elements;
      elements.reserve(numnails);
      for(int i=0; i<numnails; ++i) {
         elements.push_back(i+1);
      }

      std::deque<std::vector<int>> results = GenAll(elements);
   
      clock_t end = clock();
      double dur = double(end-start)/CLOCKS_PER_SEC;
      if (argc >= 2) {
         //print results
         if (results.size() < 33) {
            std::cout << '\n';
            for(unsigned int i = 0; i < results.size(); i++) {
               std::cout << '{';
               for(unsigned int j = 0; j < results[i].size(); j++) {
                  if (results[i][j] < 0)
                     std::cout << '-';
                  else
                     std::cout << '+';
                  std::cout << char('A'+abs(results[i][j])-1);
               }
               std::cout << '}' << '\n';
            }
            std::cout << '\n';
         }
      }

      std::cout << "numnails: " << numnails << '\n';
      std::cout << "solutions:" << results.size() << '\n';
      std::cout << "elapsed:" << (int)dur/3600 << ':' << (int)dur%3600/60 << ':' << (int)dur%60 << std::endl;
   }

   char wait;
   std::cin >> wait;

   return 0;
}

[edit] Updated code to generate all commutator solutions. No non-commutator rotations.[/edit]
[edit] Replaced several vectors with deque's, got 4x speedup for 13 elements. Also, corrected inverses.[/edit]
Last edited by Ambeco on Tue Aug 16, 2011 7:22 pm UTC, edited 5 times in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: O(you make baby Jesus cry)

Postby Yakk » Thu Aug 04, 2011 7:27 pm UTC

Blatm wrote:My math problem is: consider a free group [imath]G[/imath] generated by [imath]a_1[/imath], [imath]a_2[/imath], ..., [imath]a_n[/imath]. Define [imath]\phi_i[/imath]: [imath]G \rightarrow G[/imath] as [imath]\phi_i(a_i) = \phi_i(a_i^{-1}) = e[/imath] (the identity), [imath]\phi_i(a_j) = a_j[/imath] for [imath]i \neq j[/imath] (and similarly for the inverses of generators), and [imath]\phi_i(gh) = \phi_i(g) \phi_i(h)[/imath] for all [imath]g, h[/imath] in [imath]G[/imath]. For example, [imath]\phi_2(a_1 a_2 a_1 a_2^{-1}) = a_1^2[/imath]. The problem is to find elements of this group [imath]g[/imath] such that [imath]g \neq e[/imath], but for every [imath]i[/imath], [imath]\phi_i(g) = e[/imath].

A few issues. I assume that your [imath]g[/imath] = [imath]G[/imath] (the case is an error?)?

So you have a family of group-friendly morphisms [imath]phi_i[/imath], each of which maps the corresponding free group element [imath]a_i[/imath] to the identiy, and leaves the other free group elements stationary.

You want to find a non-trivial element that is mapped to the identity by all [imath]phi_i[/imath].

In effect, you want a group element such that, when you remove any one a_i (and its inverse) from it, the element "collapses" to the identity.

Lets look at the commutator as our base operation. If we have [a,b] and either a or b "collapses" to the identity under the map phi_i, then [a,b] collapses under phi_i.

Because the notation works out better, lets use a post-fix notation for our commutator. Ie, a,b[] is [a,b].

Lets take an 2^n dimensional free group. The sequence:
a_0 a_1[] a_2 a_3[] [] a_4 a_5 [] a_6 a_7 [] [] [] a_8 a_9 [] a_10 ...
will thus collapse under each phi_i. (this is a balanced binary tree of the generators expanded under the operation []).

Note that for groups that lack 2^n generators, you could build a slightly off balance binary tree that you collapse using [] and also get a somewhat short result.

I'd be tempted to approach a proof that an operation like [] is required by taking an arbitrary string that doesn't use the []-based structure yet collapses, and see if you can shorten it somehow?
Last edited by Yakk on Fri Aug 05, 2011 1:46 pm UTC, edited 1 time in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: O(you make baby Jesus cry)

Postby Blatm » Fri Aug 05, 2011 7:18 am UTC

Yakk: I see no errors in the part of my OP that you quote. [imath]g[/imath] is a group element of the free group [imath]G[/imath]. Despite the misunderstanding it looks like you understand the problem. I agree that the solution you give works. It would be very nice to show that the shortest solutions are always dependent on []. You can show that the shortest solution is of the form [imath]g,h[][/imath] for some [imath]g[/imath] and [imath]h[/imath] if you can show that there is an [imath]a_i[/imath] that appears only once in the solution.

Ambeco: Thanks very much for the replies. Unfortunately I think you misunderstood the problem, though the code you've written looks like it'll be useful. I'm not very experienced with C++ so I'll have to read your code carefully to understand it (e.g. I know what break does but not what struct means).

The problem is about groups, which are sets plus a binary operation (e.g. the integers under addition form a group). To rephrase, groups are just sets where you can operate/"multiply" (for lack of a better word) the elements together (which definition requires are also in the group). The [imath]a_i[/imath]'s and stuff are just elements of this group. The operation is often not written which is why it looks like multiplication. It follows the same conventions as multiplication, e.g. just like in the context of real numbers writing [imath]pq = r[/imath] means you get a new number [imath]r[/imath] by applying the binary operation multiplication to [imath]p[/imath] and [imath]q[/imath], [imath]a_1 a_2 = g[/imath] means you get a new group element [imath]g[/imath] by applying the binary operation of the group to [imath]a_1[/imath] and [imath]a_2[/imath], which were group elements to begin with. Another important property of groups is that they always have an identity element, i.e. an element, usually denoted [imath]e[/imath] where I'm from, but [imath]\epsilon[/imath] and [imath]1[/imath] both seem like reasonable alternatives, such that [imath]ge = eg = g[/imath] for any [imath]g[/imath] in the group. Moreover groups require that for every element [imath]g[/imath] in the group there is a [imath]g^{-1}[/imath] such that [imath]gg^{-1} = e[/imath].

The particular group I want to consider is the one where every element can be expressed uniquely as the product of [imath]a_1[/imath] through [imath]a_n[/imath], which are called generators (group operations are associative but not necessarily commutative (and not in this case)). That's why my elements all look like they do. My question is, informally, are there elements [imath]g[/imath] in this group such that [imath]g \neq e[/imath], but that if you remove any [imath]a_i[/imath] and its inverse then "[imath]g[/imath]" (quotes since it's not really [imath]g[/imath] anymore) becomes [imath]e[/imath]. For example [imath]a_1 a_2 a_1^{-1}[/imath] becomes [imath]a_1 a_1^{-1} = e[/imath] if you remove [imath]a_2[/imath] and its inverse (which is absent), but not if you remove [imath]a_1[/imath] and its inverse; it just becomes [imath]a_2[/imath]. [imath]a_1 a_2 a_1^{-1} a_2^{-1}[/imath] is a solution if the group is generated by [imath]a_1[/imath] and [imath]a_2[/imath], but not if it's generated by [imath]a_1[/imath], [imath]a_2[/imath], and [imath]a_3[/imath], since removing [imath]a_3[/imath] does nothing. The [imath]\phi_i[/imath] business is formalizing the idea of "removing an [imath]a_i[/imath]": [imath]\phi_i(g)[/imath] is [imath]g[/imath] with [imath]a_i[/imath] and its inverse removed. [imath]a_1 a_1^{-1} a_2 a_2^{-1} ... a_n a_n^{-1}[/imath] is not a solution because it is already [imath]e[/imath].

The five shortest length solutions to the 3 generator problem are:
[imath]a_1 a_2 a_3 a_2^{-1} a_1^{-1} a_2 a_1 a_3^{-1} a_1^{-1} a_2^{-1}[/imath]
[imath]a_1 a_2 a_3 a_2^{-1} a_3^{-1} a_1^{-1} a_3 a_2 a_3^{-1} a_2^{-1}[/imath]
[imath]a_1 a_2 a_1^{-1} a_3 a_1 a_3^{-1} a_2^{-1} a_3 a_1^{-1} a_3^{-1}[/imath]
[imath]a_1 a_2 a_1^{-1} a_3 a_1 a_2^{-1} a_1^{-1} a_2 a_3^{-1} a_2^{-1}[/imath]
[imath]a_1 a_2 a_1^{-1} a_2^{-1} a_3 a_2 a_1 a_2^{-1} a_1^{-1} a_3^{-1}[/imath]

My program will output these as
1 2 3 -2 -1 2 1 -3 -1 -2
1 2 3 -2 -3 -1 3 2 -3 -2
1 2 -1 3 1 -3 -2 3 -1 -3
1 2 -1 3 1 -2 -1 2 -3 -2
1 2 -1 -2 3 2 1 -2 -1 -3

(These are all "rotations" of one solution, but the relabeling of the generators makes that not so easy to see.)*

The last solution is F(ABC) = {F(AB) C F(-B-A) -C} in your notation (note the reversed -A and -B in the second F( ) in the set) if I'm not mistaken. A lot of the outputs of your program are very close to being solutions, and this is what makes me think that your code could be very useful with just a few tweaks. One fear that I have, which may be unfounded because again I don't fully understand your code yet (and let me know if it is), is that from the way you're describing it it sounds like all the solutions might be built up from "smaller" solutions (solutions for fewer generators), and I don't want to assume that that's always the case without a theorem to tell me it is.

*By "rotation" what I mean is taking generator/generator inverses from the end and putting them at the beginning, e.g. [imath]a_1 a_2 a_3 a_2[/imath] and [imath]a_2 a_1 a_2 a_3[/imath] are rotations of one another. It turns out that rotations of a solution are also solutions. If there are ridiculous number of solutions this is where they could be cut down. For 3 generators it's just multiplies the number of solutions by 10 (since they have length 10), but for 4 generators you get solutions like [imath][a_4,S_3][/imath] (I define [imath][a,b] = aba^{-1}b^{-1}[/imath]), where [imath]S_3[/imath] is a solution to the 3 generator problem. These have length 22, so you get 22 solutions for a particular [imath]S_3[/imath], and there are 10 [imath]S_3[/imath]'s. Some of these will probably overlap or not be acceptable for another reason already instated, but the number of solutions which are essentially the same will grow quickly this way (O(exp(n^2))?) and I would rather associate them just like I associate solutions which are the same up to renaming generators.

I've been working on optimizing my original program (veery slowly) going in a completely different direction. I'd rather focus my attention on your code though because I expect it'll probably be a good deal more efficient and it's shorter.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: O(you make baby Jesus cry)

Postby Yakk » Fri Aug 05, 2011 1:49 pm UTC

Bah, sorry. I read "elements of this group, g", not "elements of this group, such as g".
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Fri Aug 05, 2011 7:23 pm UTC

Blatm wrote:I know what break does but not what struct means.

Code: Select all

struct rectangle{
    int height;
    int width;
};
rectangle doubleit(rectangle r) {
    r.width = r.width * 2;
    r.height = r.height * 2;
    return r;
}
int main() {
    rectangle mousepad;
    mousepad.width = 10;
    mousepad.height = 8;
    mousepad = doubleit(mousepad);
    std::cout << "width:" << mousepad.width << " height:" << mousepad.height << '\n';
    //outputs   "width:20 height:16"
}
The simplist way to think of a struct is simply "a group of variables" that can be used more or less like any other type. (In C, that's exactly what it is. In C++, they can be much more. For instance, in my code I gave them functions.) Here, I make a new variable type called rectangle, that is made of two integers, named height, and width.
Blatm wrote:The problem is about groups, which are sets plus a binary operation (e.g. the integers under addition form a group).
So, yes, the math is above my education (though barely, by the looks of it). I'll look them up.
Blatm wrote:1 2 3 -2 -1 2 1 -3 -1 -2
1 2 3 -2 -3 -1 3 2 -3 -2
1 2 -1 3 1 -3 -2 3 -1 -3
1 2 -1 3 1 -2 -1 2 -3 -2
1 2 -1 -2 3 2 1 -2 -1 -3
In theory, my program would only have generated the second as [1[23]], and fifth as [[12]3]. (in reality, I just noticed a bug where it wont have generated the [1[23]], but it's easily corrected. I'll get to that later.)
Blatm wrote:One fear that I have, which may be unfounded because again I don't fully understand your code yet (and let me know if it is), is that from the way you're describing it it sounds like all the solutions might be built up from "smaller" solutions (solutions for fewer generators), and I don't want to assume that that's always the case without a theorem to tell me it is.
That is exactly the assumption I made. Without it, I don't understand enough of the math to help.
Blatm wrote:*By "rotation" what I mean is taking generator/generator inverses from the end and putting them at the beginning...
I hadn't noticed that, so my code won't generate most rotations of the answers it finds.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: O(you make baby Jesus cry)

Postby jestingrabbit » Sat Aug 06, 2011 3:16 pm UTC

Blatm wrote:Yakk: I see no errors in the part of my OP that you quote. [imath]g[/imath] is a group element of the free group [imath]G[/imath]. Despite the misunderstanding it looks like you understand the problem. I agree that the solution you give works. It would be very nice to show that the shortest solutions are always dependent on []. You can show that the shortest solution is of the form [imath]g,h[][/imath] for some [imath]g[/imath] and [imath]h[/imath] if you can show that there is an [imath]a_i[/imath] that appears only once in the solution.


Is this what you're trying to work out, whether or not these elements are always built up by commutators? Its certainly the elegant hypothesis, but imo it'd be wildly more interesting if there are solutions that didn't look like that for some n. You can pretty easily work out the shortest strings of this kind that are generated by the commutator, perhaps just look at the strings that are 2 shorter than that? not much of an improvement, I know.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: O(you make baby Jesus cry)

Postby Token » Sat Aug 06, 2011 11:30 pm UTC

jestingrabbit wrote:Is this what you're trying to work out, whether or not these elements are always built up by commutators? Its certainly the elegant hypothesis, but imo it'd be wildly more interesting if there are solutions that didn't look like that for some n.

Well, even for the 3-element case, you have solutions like [imath]aba^{-1}cab^{-1}a^{-1}bc^{-1}b^{-1}[/imath] which aren't of the form [g,h] (though it is a rotation of such a solution). So it feels like commutators may be the wrong way to attack this - though I suspect it may well be the case that minimum-length commutator solutions are in fact minimum-length overall, even if they aren't the only such solutions.

Some brief, non-commutator observations - firstly, any rotation of a solution is itself a solution (pretty easy to show). Two consequences of this are that any minimum-length solution is cyclically reduced, and that no minimum-length solution has two instances of the same generator adjacent to each other (if you rotate the two instances to the front of the string, you have a solution of the same length, and if you remove the first instance of the generator and the last instance of its inverse, you have a shorter solution). These might help in reducing the number of cases the program needs to check?
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Thu Aug 11, 2011 7:24 pm UTC

As an aside, I fixed my code that generates "the derived group" of G (I read http://en.wikipedia.org/wiki/Group_(mathematics) and http://en.wikipedia.org/wiki/Commutator finally)!

I basically get stuck on: why does [imath]a_ia_ja_i^{-1}a_j^{-1}[/imath] ALWAYS reduce to [imath]e[/imath], unless the group is communitive, which would allow more solutions? If g is [imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1}[/imath], then
[math]\phi_3(g)[/math][math]=\phi_3(a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1})[/math][math]=\phi_3(a_1)\phi_3(a_2)\phi_3(a_1^{-1})\phi_3(a_2^{-1})\phi_3(a_3)\phi_3(a_1)\phi_3(a_2)\phi_3(a_1^{-1})\phi_3(a_2^{-1})\phi_3(a_3^{-1})[/math](is that the right way to expand?)[math]=a_1a_2a_1^{-1}a_2^{-1}a_1a_2a_1^{-1}a_2^{-1}[/math]
and I don't see how this reduces to [imath]e[/imath], without also allowing [imath]a_1a_2a_3a_3^{-1}a_2^{-1}a_1^{-1}[/imath] as a solution. I also don't see from your original description why
[imath]a_1a_1^{-1}a_2a_2^{-1}a_3a_3^{-1}[/imath] doesn't seem to be valid.

If the clarification I'm requesting is already clear to people who studied group theory, then I'll back off the math and stick to the code. This thread isn't about my problems, it's about yours.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: O(you make baby Jesus cry)

Postby Yakk » Thu Aug 11, 2011 7:42 pm UTC

Let X, Y be a group, and e_y be the identity of Y.

Let f:X->Y be a group homomorphism. This means that for any elements x,y of X, we have f(xy) = f(x)f(y), and f(x^-1) = f(x)^-1.

Let c_x be a value such that f(c_x) = e_y (and thus f(c_x^-1) = e_y as well).

Let b_x be any element of X. Then f([c_x, b_x]) = f( c_x b_x c_x^-1 b_x^-1 ) = f(c_x) f(b_x) f(c_x^-1) f(b_x^-1) = e_y f(b_x) e_y f(b_x)^-1 = f(b_x) f(b_x)^-1 = e_y

Now, each Phi_i maps one of the root elements (a_i) to the identity. The trick with the commutators is that we "chain" everything together so that each Phi_i causes either the left or right "branch" of the "root" branch of the tree of commutators to map to e, and thus causes the entire expression to map to e.

Now, we need this to happen to each Phi_i, so we build a tree out of commutators with each a_i somewhere in it. The term that contains the a_i maps to e under the Phi_i, which then cause the commutator one level up to also map to e, all the way to the root.

Now, what you might be missing is that we chain these together. So at level 3, we start with:

[a_1, [a_2, a_3]] = [a_1, a_2 a_3 a_2^-1 a_3^-1] = a_1 a_2 a_3 a_2^-1 a_3^-1 a_1^-1 (a_2 a_3 a_2^-1 a_3^-1)^-1
those brackets matter. Now:
(a_2 a_3 a_2^-1 a_3^-1)^-1 = a_3^-1^-1 a_2^-1^-1 a_3^-1 a_2^-1 = a_3 a_2 a_3^-1 a_2^-1
which is a useful trick that you can verify by inspection (reverse the order of multiplication and apply ^-1 to each component).

So we get:
[a_1, [a_2, a_3]] = a_1 a_2 a_3 a_2^-1 a_3^-1 a_1^-1 a_3 a_2 a_3^-1 a_2^-1
We then apply Phi_3 to this:
Phi_3(a_1 a_2 a_3 a_2^-1 a_3^-1 a_1^-1 a_3 a_2 a_3^-1 a_2^-1)
= a_1 a_2 e a_2^-1 e a_1^-1 e a_2 e a_2^-1
= a_1 a_2 a_2^-1 a_1^-1 a_2 a_2^-1
= a_1 e a_1^-1 e
= a_1 a_1^-1
= e

Now, we can make this less messy by noting that, for a 'morphism f(.), f([a,b]) = [f(a), f(b)], and [a, e] = a if e is the identity.

So Phi_3( [a_1, [a_2, a_3]] )
= [Phi_3(a_1), Phi_3([a_2, a_3])]
= [Phi_3(a_1), [Phi_3(a_2), Phi_3(a_3)]]
= [Phi_3(a_1), [Phi_3(a_2), e]]
= [Phi_3(a_1), e]
= e
regardless of what Phi_3 maps a_1 and a_2 to (as it happens, we may know what it maps to -- but we don't need to know that).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Fri Aug 12, 2011 11:41 pm UTC

Unfortunately, that's a very detailed answer of most of the parts that makes sense to me, except for
[a, e] = a if e is the identity
if a is a [] set thing.
Can you edit that to show a breakdown of Phi_1 of [a_1, [a_2, a_3]] instead? That's the part where my brain broke down. Phi_2 and Phi_3 I got.
(Also, now I see why stack overflow lets me edit other people's posts. I could totally go through and add the imath's myself :[ )

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: O(you make baby Jesus cry)

Postby Blatm » Sat Aug 13, 2011 10:30 pm UTC

Ambeco wrote:As an aside, I fixed my code that generates "the derived group" of G (I read http://en.wikipedia.org/wiki/Group_(mathematics) and http://en.wikipedia.org/wiki/Commutator finally)!

I basically get stuck on: why does [imath]a_ia_ja_i^{-1}a_j^{-1}[/imath] ALWAYS reduce to [imath]e[/imath], unless the group is communitive, which would allow more solutions? If g is [imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1}[/imath], then
[math]\phi_3(g)[/math][math]=\phi_3(a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1})[/math][math]=\phi_3(a_1)\phi_3(a_2)\phi_3(a_1^{-1})\phi_3(a_2^{-1})\phi_3(a_3)\phi_3(a_1)\phi_3(a_2)\phi_3(a_1^{-1})\phi_3(a_2^{-1})\phi_3(a_3^{-1})[/math](is that the right way to expand?)[math]=a_1a_2a_1^{-1}a_2^{-1}a_1a_2a_1^{-1}a_2^{-1}[/math]
and I don't see how this reduces to [imath]e[/imath], without also allowing [imath]a_1a_2a_3a_3^{-1}a_2^{-1}a_1^{-1}[/imath] as a solution. I also don't see from your original description why
[imath]a_1a_1^{-1}a_2a_2^{-1}a_3a_3^{-1}[/imath] doesn't seem to be valid.

If the clarification I'm requesting is already clear to people who studied group theory, then I'll back off the math and stick to the code. This thread isn't about my problems, it's about yours.


It looks like you understand how the [imath]\phi[/imath]'s work. [imath]a_i a_j a_i^{-1} a_j^{-1}[/imath] is not [imath]e[/imath], but [imath]\phi_i(a_i a_j a_i^{-1} a_j^{-1}) = \phi_j(a_i a_j a_i^{-1} a_j^{-1}) = e[/imath]. (Because of this [imath]a_1 a_2 a_1^{-1} a_2^{-1}[/imath] is a solution for two generators.)

You're right that [imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1}[/imath] is not a solution for 3 generators. [imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_2a_1a_2^{-1}a_1^{-1}a_3^{-1}[/imath] is. For clarity I rewrite them one above the other:

[imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_1a_2a_1^{-1}a_2^{-1}a_3^{-1}[/imath]
[imath]a_1a_2a_1^{-1}a_2^{-1}a_3a_2a_1a_2^{-1}a_1^{-1}a_3^{-1}[/imath]

If you check this one the way you did you'll find it is indeed a solution. This solution is [imath][[a_1,a_2],a_3][/imath], and I verify that it's a solution below in two different ways.

I'll expand [imath][[a_1, a_2], a_3][/imath], [imath]\phi_3([[a_1, a_2], a_3])[/imath], and [imath][g,e][/imath] now, though it seems like you understand what's going on. You're right that [imath][g,e] = e[/imath], not [imath]g[/imath]. Note that [imath](ab)^{-1} = b^{-1} a^{-1}[/imath] and not [imath]a^{-1} b^{-1}[/imath] (a common mistake).

[math][[a_1, a_2], a_3][/math]
[math]= [a_1, a_2] a_3 [a_1, a_2]^{-1} a_3^{-1}[/math]
[math]= (a_1 a_2 a_1^{-1} a_2^{-1}) a_3 (a_1 a_2 a_1^{-1} a_2^{-1})^{-1} a_3^{-1}[/math]
[math]= a_1 a_2 a_1^{-1} a_2^{-1} a_3 a_2 a_1 a_2^{-1} a_1^{-1} a_3^{-1}[/math]

To evaluate [imath]\phi_3([[a_1, a_2], a_3])[/imath] we could use the last line of the above computation, i.e.

[math]\phi_3([[a_1, a_2], a_3]) = \phi_3(a_1 a_2 a_1^{-1} a_2^{-1} a_3 a_2 a_1 a_2^{-1} a_1^{-1} a_3^{-1})[/math]
[math]= a_1 a_2 a_1^{-1} a_2^{-1} e a_2 a_1 a_2^{-1} a_1^{-1} e[/math]
[math]= a_1 a_2 a_1^{-1} a_1 a_2^{-1} a_1^{-1}[/math]
[math]= a_1 a_2 a_2^{-1} a_1^{-1}[/math]
[math]= a_1 a_1^{-1}[/math]
[math]= e[/math]

Or we could use the trick that Yakk outlined,

[math]\phi_3([[a_1, a_2], a_3]) = [\phi_3([a_1, a_2]), \phi_3(a_3)][/math]
[math]= [\phi_3([a_1, a_2]), e][/math]
[math]= \phi_3([a_1, a_2]) \phi_3([a_1, a_2])^{-1}[/math]
[math]= e[/math]


Here's [imath][g,e][/imath] just to be sure:

[math][g,e][/math]
[math]g e g^{-1} e^{-1}[/math]
[math]g g^{-1}[/math]
[math]e[/math]



I've written another program to do what I set out to do. It's a bit buggy but much faster. The main problem however is with memory, just like Ambeco's program. What I'm doing is generating all the strings/elements that might be a solution (which is fewer than in the original since I'm requiring they satisfy certain properties) and then checking each one. Because there are so many elements the memory use is prohibitive. I think instead I should check each element as I create it and discard it if it's no good. I've been a bit busy so the work has been slow. I'll clean up my code a bit before posting it.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: O(you make baby Jesus cry)

Postby Yakk » Mon Aug 15, 2011 2:01 pm UTC

Ambeco wrote:Unfortunately, that's a very detailed answer of most of the parts that makes sense to me, except for
[a, e] = a if e is the identity
if a is a [] set thing.
Can you edit that to show a breakdown of Phi_1 of [a_1, [a_2, a_3]] instead? That's the part where my brain broke down. Phi_2 and Phi_3 I got.
(Also, now I see why stack overflow lets me edit other people's posts. I could totally go through and add the imath's myself :[ )

Oops. [a,e] = e if e is the idenity.

To derive this, we have:
aea^-1e^-1 = ae a^-1 e = a a^-1 = e

Do you understand why
f( [a,b] ) = [f(a), f(b)] ?

I'll start with that.
Phi_1( [a_1, [a_2, a_3]] )
= [ Phi_1(a_1), Phi_1([a_2, a_3]) ]
= [ e, Phi_1([a_2, a_3]) ]
Let x = Phi_1([a_2, a_3]). (I'm defining x to mean whatever value that is).
= [ e, x ]
now, we use the definition of []:
= e x e^-1 x^-1
as e^-1 = e,
= e x e x^-1
as e x = x, and e x^-1 = x^-1
= x x^-1
and, by the definition of inverse:
= e

Now, the thing that makes this less messy is the f( [a, b] ) = [f(a), f(b)], the x-substitution "trick".

We can show the first by the following. Assume f(ab) = f(a) f(b), and f(a^-1) = f(a)^-1. Then:
[f(a), f(b)] = f(a) f(b) f(a)^-1 f(b)^-1
and
f([a,b]) = f( a b a^-1 b^-1 ) = f(a) f(b) f(a^-1) f(b^-1) = f(a) f(b) f(a)^-1 f(b)^-1 = [f(a), f(b)]
And that is our proof that f([a,b]) = [f(a), f(b)], if f is sufficiently nice. Now that we have proven that, we don't have to do every step in the middle every time.

The next thing that might have caught you is that:
(a b c)^-1 != a^-1 b^-1 c^-1 (!= means "not equal), or at least not always.
Instead
(a b c)^-1 = c^-1 b^-1 a^-1
You can see this by simple multiplication:
( a b c) (c^-1 b^-1 a^-1)
= a b c c^-1 b^-1 a^-1
= a b b^-1 a^-1
= a a^-1
= e
(where e is the identity).

This also works if we reverse the order of multiplication, as the adjacent a's cancel, then the now-adjacnet b's cancel.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: O(you make baby Jesus cry)

Postby Ambeco » Mon Aug 15, 2011 5:40 pm UTC

Blatm wrote:Note that [imath](ab)^{-1} = b^{-1} a^{-1}[/imath] and not [imath]a^{-1} b^{-1}[/imath] (a common mistake).
Oh my gosh, really? Seriously? Well that's been the source of my misunderstanding then. Wow. I have to go double-check my code again but I bet this part is wrong in every "solution".
Did I ever ask why [imath]a_1a_1^{-1}a_2a_2^{-1}[/imath] wasn't a solution? Because that's always bugged me.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: O(you make baby Jesus cry)

Postby Yakk » Mon Aug 15, 2011 6:41 pm UTC

Ambeco wrote:
Blatm wrote:Note that [imath](ab)^{-1} = b^{-1} a^{-1}[/imath] and not [imath]a^{-1} b^{-1}[/imath] (a common mistake).
Oh my gosh, really? Seriously? Well that's been the source of my misunderstanding then. Wow. I have to go double-check my code again but I bet this part is wrong in every "solution".
Did I ever ask why [imath]a_1a_1^{-1}a_2a_2^{-1}[/imath] wasn't a solution? Because that's always bugged me.

it isn't a solution because it is already e (the a_i's cancel with their inverses immediately), and the question is to find non-identity elements that map to e under each Phi_i.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 2 guests