User subshift - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T21:47:23Z http://mathoverflow.net/feeds/user/728 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63435/equivalent-subshifts/63436#63436 Answer by subshift for Equivalent subshifts subshift 2011-04-29T16:26:58Z 2011-04-29T16:26:58Z <p>The paper <em><a href="http://www-users.math.umd.edu/~mmb/open/" rel="nofollow">Open Problems in Symbolic Dynamics</a></em> by Mike Boyle discusses the conjugacy problem for shifts of finite type and sofic shifts.</p> <p>More details can be found in books such as <em><a href="http://www.math.washington.edu/SymbolicDynamics/" rel="nofollow">An Introduction to Symbolic Dynamics and Coding</a></em>.</p> http://mathoverflow.net/questions/62130/whats-the-difference-between-2-and-3/62134#62134 Answer by subshift for What's the difference between 2 and 3? subshift 2011-04-18T15:29:50Z 2011-04-18T15:40:08Z <p>More examples are given as answers to <a href="http://cstheory.stackexchange.com/questions/5251/geometric-problems-that-are-np-complete-in-r3-but-tractable-in-r2" rel="nofollow">a similar question</a> about problems NP-hard in $\mathbb R^3$ but not in $\mathbb R^2$:</p> <ul> <li>Set-cover by half-spaces.</li> <li>Finding a shortest path between two points among polygonal obstacles.</li> <li>Determining whether a non-convex polygon/polyhedron can be triangulated without Steiner points.</li> <li>Realizability problem for $d$-dimensional polytopes is a candidate ($d \leq 3$ vs $d \geq 4$).</li> </ul> http://mathoverflow.net/questions/57166/computational-software-in-algebraic-topology/57188#57188 Answer by subshift for Computational software in Algebraic Topology? subshift 2011-03-03T00:56:17Z 2011-03-03T00:56:17Z <p>Sage allows you to play with simplicial complexes and their (co)homology.</p> <p><a href="http://www.sagemath.org/doc/reference/sage/homology/simplicial_complex.html" rel="nofollow">http://www.sagemath.org/doc/reference/sage/homology/simplicial_complex.html</a></p> <p><a href="http://www.sagemath.org/doc/reference/sage/homology/examples.html" rel="nofollow">http://www.sagemath.org/doc/reference/sage/homology/examples.html</a></p> http://mathoverflow.net/questions/48299/more-open-problems/48348#48348 Answer by subshift for More open problems subshift 2010-12-05T07:16:35Z 2010-12-05T07:16:35Z <p>Mike Boyle's <a href="http://www-users.math.umd.edu/~mmb/open/" rel="nofollow">open problems in symbolic dynamics</a>.</p> http://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces Cutting a rectangle into an odd number of congruent pieces subshift 2010-01-14T14:24:22Z 2010-08-20T00:46:02Z <p>We are interested in tiling a rectangle with copies of single tile (rotations and reflexions are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.</p> <p>What happens when we ask the pieces not to be rectangular?</p> <p>For an even number of pieces, this is easy again (cut it into rectangles, and then cut every rectangle in two through its diagonal. Other tilings are also easy to find).</p> <p>The interesting (and difficult) case is tiling with an <strong>odd</strong> number of <strong>non-rectangular</strong> pieces.</p> <p>Some questions:</p> <ul> <li>Can you give examples of such tilings?</li> <li>What is the smallest (odd) number of pieces for which it is possible?</li> <li>Is it possible for every number of pieces? (<em>e.g.</em>, with five)</li> </ul> <p>There are two main versions of the problem: the polyomino case (when the tiles are made of unit squares), and the general case (when the tiles can have any shape). The answers to the above questions might be different in each case.</p> <p>It seems that it is impossible to do with three pieces (I have some kind of proof), and the smallest number of pieces I could get is $15$, as shown above:</p> <p><img src="http://thevelho88.free.fr/bazar/15.png" alt="alt text"></p> <p>This problem is very useful for spending time when attending some boring talk, etc.</p> http://mathoverflow.net/questions/1194/how-to-partition-r3-into-pairwise-non-parallel-lines How to partition R^3 into pairwise non-parallel lines? subshift 2009-10-19T10:18:26Z 2010-07-07T16:22:04Z <p><strong>Problem.</strong> How to partition R^3 into pairwise non-parallel lines?</p> <p>A possible solution is to stack infinitely many concentric'' hyperboloids, by increasing radius and decreasing slope. And don't forget the line on the $z$ axis at the center. The prototype hyperboloid <a href="http://www-lm.ma.tum.de/archiv/sos04/la2lb04/Regel%5FHyperboloid.gif" rel="nofollow">looks like this</a>.</p> <p>I heard a talk to which I didn't understand a lot ; a solution was given using hopf fibration. I'm not familiar to these notions, and at the end it went like Tadaa! And here is our partition!''. The speaker could not describe what the partition looks like.</p> <p>I would be very glad to: (1) understand the math he did (article, book?), (2) see what his solution looks like, and (3) know what kind of solutions exist.</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/9879/using-tikz-in-papers/20695#20695 Answer by subshift for Using TikZ in papers subshift 2010-04-08T06:30:43Z 2010-04-08T06:30:43Z <p>You can try "Shippage.sty", <a href="http://www.lif.univ-mrs.fr/~nollinge/hack/tex/" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces/12239#12239 Answer by subshift for Cutting a rectangle into an odd number of congruent pieces subshift 2010-01-18T21:50:06Z 2010-01-20T22:08:02Z <p>I am posting the 11 pieces solution shown in the article cited by Michael (it is not freely available online).</p> <p><img src="http://thevelho88.free.fr/bazar/11.png" alt="alt text" /></p> <p>This is the smallest known number of pieces. Some remarks:</p> <ul> <li>The question is <strong>open</strong> for 5, 7, or 9 pieces. Get your pencils!</li> <li>Everything so far is with polyominoes. Any suggestion with more complicated shapes?</li> <li>Unlike the other solution I posted, this one cannot be resized along the $x$ or $y$ axis.</li> </ul> http://mathoverflow.net/questions/2144/a-single-paper-everyone-should-read/2499#2499 Answer by subshift for A single paper everyone should read? subshift 2009-10-25T19:20:12Z 2009-10-25T19:20:12Z <p>Another suggestion: <a href="http://arxiv.org/abs/0712.1320" rel="nofollow"><em>A beginner's guide to forcing</em></a> by Tim Chow.</p> <p>It really explains the continuum hypothesis, in a very accessible and captivating way. People often talk about the continuum hypothesis, but it's nice to know what's going on for real.</p> http://mathoverflow.net/questions/2144/a-single-paper-everyone-should-read/2325#2325 Answer by subshift for A single paper everyone should read? subshift 2009-10-24T17:56:34Z 2009-10-24T17:56:34Z <p>I like <a href="http://arxiv.org/abs/0711.1873" rel="nofollow"><em>Musical Actions of Dihedral Groups</em></a> pretty much. It gives a nice view of harmony (the art of using chords in music), considering the set of chords as the dihedral group of order 24 (12 major + 12 minor). </p> <p>Unfortunately, this is useful only for people into music <em>and</em> maths. I would also like to share it with my musician friends, but most of them will probably run away at the sight of the first mathematical term...</p> <p>Please don't vote down if you're not a musician ;).</p> http://mathoverflow.net/questions/2218/characterize-pnp/2221#2221 Answer by subshift for Characterize P^NP subshift 2009-10-23T23:37:21Z 2009-10-23T23:37:21Z <p>This class is also known as &#916;<sub>2</sub>P. See the <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo:D#delta2p" rel="nofollow">complexity zoo</a> for more details and results.</p> http://mathoverflow.net/questions/1017/intro-to-automatic-theorem-proving-logical-foundations/2074#2074 Answer by subshift for Intro to automatic theorem proving / logical foundations? subshift 2009-10-23T11:34:35Z 2009-10-23T11:34:35Z <p>Have you heard of the <a href="http://coq.inria.fr/" rel="nofollow">Coq proof assistant</a>? It is quite popular here in France. The official webpage contains good <a href="http://coq.inria.fr/documentation" rel="nofollow">documetation</a>.</p> http://mathoverflow.net/questions/2045/how-can-one-characterize-npsat/2055#2055 Answer by subshift for How can one characterize NP^SAT? subshift 2009-10-23T08:35:19Z 2009-10-23T08:35:19Z <p>Yes, NP^SAT = NP^NP, because SAT is complete for NP. I don't know what else can be said about this class (it's not in the <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo" rel="nofollow">complexity zoo</a>). See the <a href="http://en.wikipedia.org/wiki/Oracle%5Fmachine" rel="nofollow">wikipedia oracle page</a> for more details.</p> <p>By the way, the above "computer" tag is not very relevant, it should rather be "complexity", or "complexity-theory".</p> http://mathoverflow.net/questions/1924/what-are-some-reasonable-sounding-statements-that-are-independent-of-zfc/1958#1958 Answer by subshift for What are some reasonable-sounding statements that are independent of ZFC? subshift 2009-10-22T21:50:48Z 2009-10-22T21:50:48Z <p><a href="http://en.wikipedia.org/wiki/Paul%5FErd%C5%91s" rel="nofollow">Paul Erdős</a> proved a <a href="http://www.renyi.hu/~p%5Ferdos/1964-04.pdf" rel="nofollow">funny statement</a> about analytic functions to be equivalent to the <a href="http://en.wikipedia.org/wiki/Continuum%5Fhypothesis" rel="nofollow">continuum hypothesis</a>. The same proof can also be found in <em>Proofs from THE BOOK</em>.</p> http://mathoverflow.net/questions/1722/free-high-quality-mathematical-writing-online/1732#1732 Answer by subshift for Free, high quality mathematical writing online? subshift 2009-10-21T21:33:10Z 2009-10-21T21:33:10Z <p>Check out Allen Hatcher's <a href="http://www.math.cornell.edu/~hatcher/#anchor1772800" rel="nofollow">online books</a> (topological stuff).</p> http://mathoverflow.net/questions/1363/regular-languages-and-the-pumping-lemma/1412#1412 Answer by subshift for Regular languages and the pumping lemma subshift 2009-10-20T12:03:50Z 2009-10-20T12:03:50Z <p>Another good way to prove language L non-regular is to find a regular language A such that L∩A is non-regular.</p> <p>For example, one can take A = a*b*, and prove that L∩A = {a^nb^n : n≥0}.</p> <p>This method works because the intersection of two regular languages is always regular.</p> http://mathoverflow.net/questions/59222/importance-of-poincare-recurrence-theorem-any-example Comment by subshift subshift 2011-03-22T19:33:14Z 2011-03-22T19:33:14Z The ergodic theorems can be seen as improvements of the Poincar&#233; recurrence theorem, because they relate the time average with the space average. However, the Poincar&#233; theorem is treated first because it is not hard to prove and it is very nice. http://mathoverflow.net/questions/37963/lecture-notes-by-thurston-on-tiling/37973#37973 Comment by subshift subshift 2010-09-21T13:58:09Z 2010-09-21T13:58:09Z I got the above PDF version from Shigeki Akiyama and I am very glad that putting it on my website is useful to some people. It would be great if more people did this because trying to find a paper that is neither on the internet or in libraries can be extremely frustrating! http://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces/12239#12239 Comment by subshift subshift 2010-03-04T09:30:52Z 2010-03-04T09:30:52Z Note that this solution yields an answer with $2k + 11$ pieces, for all $k \geq 0$. http://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces/11766#11766 Comment by subshift subshift 2010-01-14T22:22:12Z 2010-01-14T22:22:12Z Thanks for these very useful references. The &quot;record&quot; dropped from 15 to 11 pieces. Questions that remain: - is it possible with 5, 7, 9, or 11 pieces? - what about arbitrary shapes of pieces? I'm happy to see that the &quot;kind of proof&quot; I have is very similar to the one found in your ref [2]. (Anyone interested in one of the articles can ask me in private because the articles are unfortunately not available online, but greedily hidden to the public.)