Flame on.

A thread recently made me angry on sage-devel:

http://groups.google.com/group/sage-devel/browse_thread/thread/cbb7a39575870636

> Do we really need Cliquer in Sage?
>

I know this comment will be pointless, as I am pretty sure those who agree with Dr. Kirkby only want a Mathematica clone for solaris (based on his recent posts) but I'm going to go ahead and flame anyway.

I am not able to count how many times I've been in a combinatorics lecture while an algorithm using max Cliques to solve the problem at hand was casually thrown into the mix.

I am also not able to understand why Nathann received such harsh backlash for pointing out something so obvious.

I am around professors every day who use C and hardly ever check their malloc's. These are the kind of people who have written full chapters in the CRC handbook of combinatorial designs, and books(plural!) on combinatorial algorithms.

I find it revolting that there would exist math software that would cut strong usable features based on code quality. This kind of policy does NOT promote code sharing among researchers.

long live purple sage

New Direction

I'm going to take this in a new direction, programming. I know that programming blogs are a dime a dozen, but this isn't for reading really. This is for communal, logged, purposeful programming. Alright, that's it.

Help a newb out with Design Theory

I have a design $D=(X,B)$ with parameters $t$-$(v,k,\lambda)$.

Let $P^*=(P,\subset)$ be the poset (P is also an abstract simplicial complex)
formed by the following construction:

1. $X \in P$.
2. $B$ is a subset of $P$. (call these facets)
3. If $Y$ is a subset of $b \in B$, then $Y$ is in $P$.

With poset relation subset.

Obviously, all $t$ subsets of $X$ are in this poset, and they have $\lambda$
facets (blocks) that contain them.

Define a new parameter $c$.

Let$ t\leq c\leq k$.
There is a smallest $i$ such that all $i$ subsets of $X$ are in $P$,
but not all $i+1$ subsets are in $P$. Call this smallest integer $c$.

For complete designs, $c$ is $k$.

Does this parameter have a name? does it have a use?

Without loss we can say $t$ is the greatest such $t$ for this design. If $twhat can we say about the number of facets(blocks) that contain these $c$ subsets? nothing?

First recursive function I've written in years.

recurse:=function(G,B,i,g,f)
  local j;
  if Size(g) = (i-1) then
    if Size(g) = Size(B) then
      return f(g);
    else
      for j in Combinations(G,B[i]-1) do
        return recurse(G,B,i+1,Concatenation(g,[j]),f);
      od;
    fi;
  else return;
  fi;
end;


global_array:=[];
fun:=function(G,B,g)
  local gset,glist,difflist,gcopy,x,L,i,j,pos,idealdifflist;
#TODO Implement FindL, code's written, just wrap it up
  L:=2;#FindL(G,B);
  gcopy:=StructuralCopy(g);
  gset:=Flat(gcopy);
  glist:=List(G);
  difflist:=ConstantArray(0,Size(G));
  idealdifflist:=ConstantArray(L,Size(G));
  idealdifflist[Position(glist,One(G))]:=0;
  # if Id is not any one of the diffs;
  if Positions(gset,One(G))<>[] then
    return;
  else
    for i in [1..Size(gcopy)] do
      Add(gcopy[i],One(G));
    od;
#generate difflist
    for i in [1..Size(gcopy)] do
      for j in Tuples(gcopy[i],2) do
        pos:=Position(glist,j[1]*j[2]^-1);
        difflist[pos]:=difflist[pos]+1;
      od;
    od;
  fi;
#verify difflist
  if difflist = idealdifflist then
    Add(global_array,g);
  fi;
end;

Splines (bill theory of OCR)

To preface this, I have only read wiki articles, and have barely skimmed them at that.

Given an experimentally found spline $S_1$ and a two dimensional spline array $SA$, we want to find the "closest fit" spline for $S_1$. The structure of $SA$ is such that each column $c$ has multiple forms of a given spline $S_c$.

Alright, and I want to apply BCH codes to do this. I'm going to take coding theory next semester, so I guess I'll just wait until then to think about this more.

Edit 1: I just came up with two ideas while laying in bed, among others coming to me right now.

1. measure correspondence of overlapping segments of splines.
2. Create a 3 dimensional graph with the z being the first derivative of the spline, another with the z being the 2nd derivative, and another with the z being the 3rd derivative.
3. Assume there are building blocks of shapes, break each spline into it's fundamental composition of shapes.
4. the input is also not just one spline, but could be several different spline interpretations.

Edit 2: Syndrome's apparently is what I need. I'll make sure to remember that when I take the class.

Edit 3(March 13, 2010): Computer Vision is a pretty large field, and this is a very mathematical approach to it, so I think I should read and play with these things before I see where this approach fits into this quite large field.

Numerical Geometry of non-rigid shapes

Numerical Geometry of Images

Learning OpenCV

NURBS

Gestalt

Abstract vs. Applied

So I'm working on two projects currently, one is extremely applied, and hopefully will be able to generate a general theory from this experimentation. The other is working on a very general theory that someone has already demonstrated to be useful. It's sort of weird. I love the general project WAY more, even though the first applied project is breaking new ground. I'm not sure what to make of that.

New Ideas.

To achieve more characterizations of designs, create classes of designs based on constructions, maybe topology or poset.

Look at Music. If we look at a song, I feel from my understanding it is a parameterized surface, such that each time value outputs different magnitudes of an array of Hz. Then a note would be just a subsurface. Then looking at patterns of repeated subsurfaces could maybe reveal something.

This is it.

I found it. Kreher wrote a moebius demystified. I need to read it, understand it, then go to SAGE and see what is implemented. If it's not, do it myself.

Topics of interest:

• Subgroup Lattice
• Subgroups(as posets)
• Some how the orbit counting lemma is involved
• Applying the moebius inversion
• Generalized $A_{t,k}$ matrices
• (Covering Arrays in the Background)

Basic Math.

Let $A,B,C \in \{0,1,\infty,\alpha\}$, be such that $g(\{A,B,C\})=\{0,1,\infty\}$. Define
\[
h(x)=h_{A,B,C}(x)=\frac{(x-A)(B-C)}{(x-C)(B-A)}.
\]
Then $h(\{A,B,C\})=\frac{1}{h}(\{A,B,C\})=\{0,1,\infty\}$.

My question is as follows: In any mapping, at all, if you have three elements mapping to the same thing those three things map to in the inverse, then all those three elements are the same, and then $\alpha$ cannot be apart of $A$, $B$, or $C$. amirite?

I'm still sick something awful. but this little bit tripped me up in the paper I'm reading, and I can't follow the proof without understanding this point.

Permutation Groups. Automata. Presentations.

I'm in that stage of being interested in something where I want to know waaaaaay more than I know right now. First, look at this problem from Peter Cameron's collection of problems:

Problem 79
The following problem in design theory comes (indirectly) from automata theory.

Let $m$ be an integer greater than 3. Does there exist a $t$-$(2m,m,λ)$ design, for some $t>1$ and some $λ>0$, with the properties

the complement of a block is a block,
the number of blocks properly divides the total number of m-subsets of the point set?
The Hadamard conjecture would imply that the answer is "yes" for all $m>3$; but perhaps there is an easier construction, since $t$ and $λ$ are not specified.

Like, take a look at this pdf.
I emailed Cameron, and he said he's writing a "substantial paper" about the links between permutation groups and Automata. Now, Automata was my first love; the hours I spent on Formal Models homework was the most fun I've had doing homework. But, I know NOTHING yet about permutation groups. I mean, sure I've had classes, but much that I read in Cameron's Permutation Groups book is new to me.

So I end the blog post with a plea to find out what this set is composed of. $G$ is a group, $A$, and $B$ are subgroups, while $\phi$ is an isomomorphism between $A$ and $B$.
\[
\langle G, t : t^{-1}at=a\phi \text{ for all }a \in A\rangle
\]
It is larger than $G$, so it could be some sort of product.

I looked up HNN on wiki, and it is supposed to be a presentation. I probably just missed where he defined his notation about presentations. Oh well, back to thinking small; I need to study more. I'm quite quite sick today; my whole body aches something fierce.

Google AI Challange.

I am going to try to participate in the Google AI Contest, writing a Tron AI. Wish me luck. From the videos, there seem to be two points in the game:

1. (Online) Trap Them / Isolate yourself.

2. (Online) Find a maximally Hamiltonian path on your isolated sub graph.

Current Ideas:

(First some preliminaries, I vision the field as a Graph, with a vertex set and edge set.)
(Concerning topic 1.)
Find min-cuts in the graph. All of them within a certain criteria.
1. If the graph is more open (larger min-cuts, with little below max) then an openly aggressive opponent strategy would seem appropriate.
2. If the graph is more closed (very low min-cuts, with several near minimal) then a shortest path to cut off more than 50% of the map would seem more appropriate.

(Concerning topic 2.)
As the game no longer depends on what the opponent does, calculate maximally covering(with exits!) successively bigger in size.

That's all for now. Off to develop topic 1.

Ich Bin Ein Gruppenpest.

So I was doing some basic Combinatorics tonight, working on a Cameron problem, and I realized I utterly fail at it.

Like, here is a skill I feel I should know by know: Given an arbitrary expression $E$ in terms of a few variables, come up with a combinatorial problem such that the $E$ is the solution.

Example.

Set $E$ to be $m!$. The answer could then be any number of things, with an acceptable answer being "How many permutations of $m$ points are there?"

However, I have something a bit more problematic at hand, and it is really close to something simple, but not quite there. I feel frustrated.

Things I would like to know about Design Theory.

I would like to know:

• All ways to get new designs from old.
• All theorems concerning automorphisms of designs.
• All Combinatorial Representation Theory.
• All Combinatorial group invariant theory.
  

Next task:

Character table from Schrier-Sims Representation.

One of the paper's I that Kreher sent me that has Cameron as an author had a line that intrigued me greatly:

The group $\text{PSL}(2,q)$ is 3-homogeneous on the projective line when $q$ is a prime power congruent to 3 modulo 4. Therefore, a set of $k$-subsets of the projective line is the block set of a $3-(q+1,k,\lambda)$ design admitting $\text{PSL}(2,q)$ for some $\lambda$ if and only if it is a union of orbits of $\text{PSL}(2,q)$. This Simple observation has led different authors to use this group for constructing 3-designs, see for example [1-3,5,7,8,10]

The part that intrigued me was the part I separated from the rest, "This simple observation." If these authors are calling this observation simple, then there MUST exist an algorithm for taking an arbitrary group acting in some way on an arbitrary number of points and turning it's orbits into designs on those points with . Then I realized that's what we did last semester, but we did it with $\lambda =1$, and we had $k$ in mind before hand, it wasn't arbitrary.

Then, In design theory, Tonchev talked about how he sent people looking for the structure of an automorphism group in a given design, and I remembered that's what Kreher said we should do for the GDD's, and I realized if people have been doing this for 20 years or more, (Kramer Mesner was in '76? so 35 years?) why is there not some computerized way of taking $t-(v,k,\lambda)$ and spitting out some things about it's automorphism group?

I've been trying to read as much as I can about character theory to see where that goes, but I just thought I'd get this written down.

Homework 3.

Proposition.
Let \[ f(x)=\frac{ax+b}{cx+d}\text{ and } g(x)=\frac{Ax+B}{Cx+D} \]be elements in $\text{LF}(2,q)$ the group of linear fractionals over $\mathbb{F}_q$.
Suppose $\det f = \det g = 1$. If $g=f$, show that $a=rA$, $b=rB$, $c=rC$, and $d=rD$ where $r=\pm1$.

Proof.
By the proof of theorem 2 that stated $\text{LF}(2,q)\cong \text{PSL}(2,q)$,
\[
\Phi\colon \text{SL}(2,q)\rightarrow \text{LF}(2,q)
\]
defined such that
\[
\Phi\left(\left[\begin{array}{cc}a&b\\c&d\end{array}\right]\right)=\frac{ax+b}{cx+d} \]
is a homomorphism. Let $\{\pm I\}=Z=\ker \Phi$ and $\alpha \in \text{SL}(2,q)$.. Then $\zeta\colon \text{SL}(2,q)/Z\rightarrow \text{LF}(2,q)$ defined as
\[
\zeta\colon \alpha Z\mapsto \Phi(\alpha)
\]
is an isomorphism by the first law of isomorphisms. $\det f = \det g = 1$ imply that
\[ \left[\begin{array}{cc}a&b\\c&d\end{array}\right],\left[\begin{array}{cc}A&B\\C&D\end{array}\right] \in \text{SL}(2,q)
\]
and $f=g$ imply that the two matrices above are in the same coset by the isomorphism of $\zeta$. Thus either $a=A,b=B,c=C,d=D$ or $a=-A, b=-B,c=-C,d=-D$, as each coset contains only two elements.