User aaron sterling - MathOverflow

Projective Plane of Order 12

2010-09-14T01:13:54Z

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can embed here because I don't have enough reputation. Anyway, here goes:

Objective: Settle the conjecture that there is no projective plane of order 12.

In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists. Now that God's Number for Rubik's Cube has been determined after just a few weeks of massive brute force search (plus clever math of symmetry), it seems to me that this longstanding open problem might be within reach. I'm hoping this question can serve as a sanity check.

The Cube was solved by reducing the total problem size to "only" 2,217,093,120 distinct tests, which could be run in parallel.

Questions:

There have been special cases of nonexistence shown (again, by computer search). Does anyone know, if we remove those and exhaustively (cleverly?) search the rest, if the problem size is on the order of the Cube search? (Maybe too much to hope for that someone knows this....)
Any partial information in this vein?

Tiling survey that updates TIlings and Patterns?

2011-03-31T20:08:39Z

Can anyone suggest a survey (or surveys) that provides an update to Tilings and Patterns by Grunbaum and Shepard? If there's a more recent book, that would be fantastic, but I don't see one.

I am most interested in the combinatorics of Wang Tilings and other square tilings, with the motivation of applying those techniques to derive upper/lower bounds to constructions in self-assembly.

Thank you.

Is there an official name for this prohibited word pattern?

2011-08-12T15:37:50Z

SECOND EDIT: This question is now essentially answered. See this blog entry for details. Thanks to everyone who commented and answered here.

EDITED TO ADD: I asked a (hopefully more pointed and understandable) version of this question on CSTheory, and got some interesting partial answers, including a connection between this discrete combinatorial problem and the Chebyshev polynomials of the second kind. Thanks to everyone here for your help.

ORIGINAL QUESTION:

In trying to design an error-correction mechanism for self-assembling systems, I have "invented" a combinatorial object that seems natural enough that it must have appeared in the literature somewhere before. However, I don't know the keywords to search on to find it. So I'm hoping someone here can point me in the right direction.

Basic idea: a subword is prohibited from appearing in a future word if it is of form a---b, where a and b appeared earlier, with the same number of letters between them.

An example on a five-letter alphabet is this:

abcd (e)
aceb (d)
beca (d)
... etc...

The set of four-letter words, where each of the four letters is chosen from the five-letter alphabet. The words are ordered as the first one, the second one, etc. For letters $a,b$ in the alphabet, once the substring $a -^i b$ appears, it can never appear again, where $-$ is a wildcard for any letter(s), and $i \geq 0$ (so $-^0$ is the empty string).

So if axyb appears anywhere on one line, where x and y are any two letters (maybe x=y, maybe not) then for all x,y axyb is prohibited to appear on any future line.

A single line like "aaaa" would be ok in some scenarios and not in others.

I'm interested if we allow letters to appear multiple times in a word, if we require each letter appear at most once, and both in results that are existential, and also algorithmic (finding lists of such words), and other properties.

What is the name of this and/or related objects? What is a standard and/or state-of-the-art reference?

Thanks very much.

Answer by Aaron Sterling for Is there an official name for this prohibited word pattern?

2011-10-10T16:56:57Z

I found a solution in the literature (Latin Squares which Contain no Repeated Digrams by E.N. Gilbert, 1965), obtained by producing a special kind of Latin square (an addition square) using two permutations that are Costas arrays. Please see a blog entry I wrote for more details.

Find the least prime so that p-1 has two factors greater than $m$ and $n$

2011-10-04T15:30:38Z

There are comments related to this question in the previous question I asked about prime numbers.

Given positive integers $m$ and $n$, what is an explicit upper bound on the least prime $p$ such that $p-1$ has factors $m+i$ and $n+j$ for some $i,j \geq 0$? In other words, some number at least as large as $m$ divides $p-1$, and so does some number at least as large as $n$.

Example:

Suppose $m=5$ and $n=4$. Then, while 23 is prime, and $23 > 20$, it does not qualify because 22 can only be factored into 11 and 2, and $2< m,n$. On the other hand, 29 is ok, because 28 can be factored into 7 and 4, both of which are at least as large as $m,n$.

Find the least prime $p$ such that $mn$ divides $p-1$

2011-10-03T16:43:11Z

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.

Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ for some $k \geq 1$.

For what I am trying to do, I need an explicit algorithm to find $p$, as opposed to an approximation. Is there a best one known? What is the upper bound on how much larger $p$ might be than $mn$? I am happy to assume that $m$ and $n$ are "sufficiently large" for the algorithm to have nice properties, if that helps.

Thank you. Hopefully the answer is obvious to everyone but me. :-)

Answer by Aaron Sterling for Has Oracles actually provided intuition for proving anything in Complexity Theory?

2011-09-27T17:50:04Z

There are probably several excellent answers to your question, but I will give you my own mediocre one.

The existence of an oracle separation means, "Nonrelativizing techniques are needed to prove something here." As there are few nonrelativizing techniques, it either tells exactly which tools to use, or tells that brand new techniques are probably needed, so pursuing work in this direction is likely to be hard. This has caused complexity theorists to open new areas of research, to be able to say something about questions whose direct answer appears very hard to obtain.

See The Role of Relativization in Complexity Theory by Fortnow for much more.

Answer by Aaron Sterling for Special cases for efficient enumeration of Hamiltonian paths on grid graphs?

2011-09-26T18:48:33Z

I can give a partial answer to the first question:

While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles?

If the grid graph is "solid," ie., has no holes, then there is a polynomial-time algorithm by Umans and Lenhart (paper here) that will find a Hamiltonian cycle, or reject the graph if no such cycle exists. The algorithm first finds a maximum matching, and then decomposes the graph into "static alternating strips," both of which can be performed efficiently. Production of the Hamiltonian cycle is achieved by changing the matching depending on how the static alternating strips are laid out.

While there may be exponentially many different H cycles, it is possible to enumerate them with polynomial delay (meaning only having to wait for a polynomial amount of time before outputting the next one) by changing the order in which one traverses the static alternating strips, and/or changing the underlying matching. (Caveat: the enumeration algorithm may need to be more careful than my handwaving, to ensure only polynomially-many duplicate cycles are outputted before a new one is. It seems, though, that one could simply build different cycles in parallel, and then prioritize the ones that deviate from one another.)

So hole-free grid graphs appear to be one such special case.

Answer by Aaron Sterling for Arithmetic of ordered sets more general than ordinals

2010-09-13T02:14:21Z

Peter Aczel's book Non-Wellfounded Sets would be my suggestion.

Comment by Aaron Sterling

2011-10-10T16:57:28Z

@Gerhard: Done. Thanks again.

Comment by Aaron Sterling

2011-10-04T15:59:56Z

@Gerhard: I see what you are saying. I will have to think about this for a bit, to make sure I am asking for what I really need. Thank you.

Comment by Aaron Sterling

2011-10-04T15:51:09Z

@Someone: hahaha!!! Yes, you have a point. Better now?

Comment by Aaron Sterling

2011-10-04T15:38:56Z

Hmm... I wish to find the smallest $p$ for which this is true of any $i$ and $j$. So $i$ and $j$ "don't matter." I will add an example to the question.

Comment by Aaron Sterling

2011-10-04T15:31:35Z

Thanks very much, everyone. I formally asked a [question](mathoverflow.net/questions/77141/…) about this second issue, because it sounds nontrivial.

Comment by Aaron Sterling

2011-10-04T15:24:27Z

@Chandan Singh Dalawat: I mean some $k$, in fact the smallest possible $k$. Now edited.

Comment by Aaron Sterling

2011-10-03T19:01:04Z

@Igor: yes, exactly.

Comment by Aaron Sterling

2011-10-03T18:42:31Z

@Igor: The reason I wrote $mn$ instead of a single value is that I had in the back of my mind another problem, which is: given $m$ and $n$, find the least prime $p$ such that $p-1=(m+i)(n+j)$ for $i,j \geq 1$. So the smallest "rectangle" of area $p-1$ that contains the rectangle $mn$. I don't know if that is a related problem, or merits a question on its own, still pondering that. I figured I should comment in case you (or someone else) knew the answer offhand.

Comment by Aaron Sterling

2011-10-03T18:14:53Z

Thanks, both of you, this is a big help.

Comment by Aaron Sterling

2011-08-17T14:34:14Z

I just had a helpful email correspondence with Sergey Kitaev, author of the book you linked. So thanks for pointing me in that direction.

Comment by Aaron Sterling

2011-08-13T14:30:58Z

Thanks very much for these. A couple I already looked at, both the others no.

Comment by Aaron Sterling

2011-08-13T14:21:53Z

@Joel: Word "abab" could be part of the set yes. But if it is, then abxx, axbx, axxb could never be added later. Also, I can see application where your intuition would be better, and "ab" could appear at most once, anywhere. I'd be grateful for an answer, either way.

Comment by Aaron Sterling

2011-08-13T13:25:56Z

Thanks very much for all the feedback! I will edit the question, and hopefully answer all questions/address all concerns, within an hour or so.

Comment by Aaron Sterling

2011-04-04T13:37:44Z

Thanks for the references. I've skimmed the non-German ones, and they look very interesting (though perhaps not immediately helpful on my current project). @Henry Cohn: Thanks for the link, I'll check it out.

Comment by Aaron Sterling

2011-04-04T13:36:46Z

@Joseph O'Rourke: Thanks very much. :-)