Changeset 458174a in git for Singular/LIB/fpaprops.lib

Timestamp:

May 2, 2018, 10:45:42 AM (6 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', 'ec94ef7a30b928574c0c3daf41f6804dff5f6b69')

Children:

0f987ab443ee33e628ea90f02a2fddfb9d8fa497

Parents:

75def9c8a4972706cb710a11c07681ad43676aed2ba25ee7ea3c483c73847576db73cb6464bc67ba

Message:

Merge branch 'spielwiese' into stable

File:

• Singular/LIB/fpaprops.lib (modified) (11 diffs)

Singular/LIB/fpaprops.lib

@@ -18 +18 @@
 
 PROCEDURES:
-  lpNoetherian(<GB>);     check whether A/<GB> is (left/right) noetherian
+  lpNoetherian(<GB>);     check whether A/<LM(GB)> is (left/right) Noetherian
   lpIsSemiPrime(<GB>);    check whether A/<LM(GB)> is semi prime
   lpIsPrime(<GB>);        check whether A/<LM(GB)> is prime
@@ -33 +33 @@
 "USAGE: lpNoetherian(G); G an ideal in a Letterplace ring
 RETURN: int
-@*      0 not noetherian
-@*      1 left noetherian
-@*      2 right noetherian
-@*      3 noetherian
-PURPOSE: Check whether A/<G> is (left/right) noetherian
+@*      0 not Noetherian
+@*      1 left Noetherian
+@*      2 right Noetherian
+@*      3 Noetherian
+@*      4 weak Noetherian
+PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian
 ASSUME: - basering is a Letterplace ring
 @*      - G is a Groebner basis
+THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>.
+If it gives an affirmative answer for one of the properties, then it 
+holds for both A/<LM(G)> and A/<G>. However, a negative answer applies 
+only to A/<LM(G)> and not necessarily to A/<G>.
+NOTE: Weak Noetherian means that two-sided ideals in A/<LM(G)> satisfy
+the acc (ascending chain condition).
 "
 {
@@ -91 +98 @@
   intvec visited;
   visited[ncols(UG)] = 0;
-  int inFlag, outFlag;
+  int inFlag, outFlag, inOutFlag;
   for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) {
-    int inOutFlags = inOrOutCommingEdgeInCycle(UG, v, visited, 0);
+    int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0);
     if (inOutFlags == 1) {
       inFlag = 1;
     }
     if (inOutFlags == 2) {
-      outFlag = 2;
+      outFlag = 1;
     }
     if (inOutFlags == 3) {
       inFlag = 1;
-      outFlag = 2;
+      outFlag = 1;
+    }
+    if (inOutFlags == 4) {
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 5) {
+      inFlag = 1;
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 6) {
+      outFlag = 1;
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 7) {
+      inFlag = 1;
+      outFlag = 1;
+      inOutFlag = 1;
     }
     kill inOutFlags;
   } kill v;
-  return (3 - inFlag - outFlag);
+  int noetherian = 3 - 1*inFlag - 2*outFlag;
+  if (noetherian == 0) {
+    return (4 - 4*inOutFlag); // weak noetherian
+  }
+  return (noetherian);
 }
 example
@@ -118 +145 @@
 }
 
-static proc inOrOutCommingEdgeInCycle(intmat G, int v, intvec visited, intvec path) {
+static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) {
   // Mark the current vertex as visited
   visited[v] = 1;
@@ -129 +156 @@
   }
 
-  int inFlag, outFlag;
+  int inFlag, outFlag, inOutFlag;
 
   for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) {
     if (G[v,w] == 1) {
-      if (visited[w] == 1) {
-        // new cycle
-        if (v == w) {
+      if (visited[w] == 1) { // new cycle
+        int tmpInFlag;
+        int tmpOutFlag;
+        if (v == w) { // cycle is a loop
           for (int u = 1; u <= ncols(G); u++) {
             if (G[v,u] && u != v) {
-              outFlag = 2;
+              outFlag = 1;
+              tmpOutFlag = 1;
             }
             if (G[u,v] && u != v) {
               inFlag = 1;
+              tmpInFlag = 1;
             }
           } kill u;
@@ -151 +181 @@
                 if (path[i] != v) {
                   if (u != path[i+1]) { // and u is not the next element in the cycle
-                    outFlag = 2;
+                    outFlag = 1;
+                    tmpOutFlag = 1;
                   }
                 } else {
                   if (u != w) {
-                    outFlag = 2;
+                    outFlag = 1;
+                    tmpOutFlag = 1;
                   }
                 }
@@ -163 +195 @@
                   if (u != path[i-1]) { // and u is not the previous element in the cylce
                     inFlag = 1;
+                    tmpInFlag = 1;
                   }
                 } else {
                   if (u != v) {
                     inFlag = 1;
+                    tmpInFlag = 1;
                   }
                 }
@@ -176 +210 @@
           } kill i;
         }
+        if (tmpInFlag > 0 && tmpOutFlag > 0) {
+          // there are both in and outcomming edges in this cycle
+          inOutFlag = 1;
+        }
+        kill tmpInFlag;
+        kill tmpOutFlag;
       } else {
-        int inOutFlags = inOrOutCommingEdgeInCycle(G, w, visited, path);
+        int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path);
         if (inOutFlags == 1) {
           inFlag = 1;
         }
         if (inOutFlags == 2) {
-          outFlag = 2;
+          outFlag = 1;
         }
         if (inOutFlags == 3) {
           inFlag = 1;
-          outFlag = 2;
+          outFlag = 1;
+        }
+        if (inOutFlags == 4) {
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 5) {
+          inFlag = 1;
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 6) {
+          outFlag = 1;
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 7) {
+          inFlag = 1;
+          outFlag = 1;
+          inOutFlag = 1;
         }
         kill inOutFlags;
@@ -193 +249 @@
   } kill w;
 
-  return (inFlag + outFlag);
+  return (1*inFlag + 2*outFlag + 4*inOutFlag);
 }
 
@@ -202 +258 @@
 ASSUME: - basering is a Letterplace ring
       - G is a Groebner basis
+THEORY: lpIsSemiPrime works with the monomial algebra A/<LM(G)>.
+A positive answer holds for both A/<LM(G)> and A/<G>, while 
+a negative answer applies only to A/<LM(G)> and not necessarily to 
+A/<G>.
 "
 {
@@ -303 +363 @@
 ASSUME: - basering is a Letterplace ring
       - G is a Groebner basis
+THEORY: lpIsPrime works with the monomial algebra A/<LM(G)>.
+A positive answer holds for both A/<LM(G)> and A/<G>, while
+a negative answer applies only to A/<LM(G)> and not necessarily to A/<G>.
 "
 {