User gray taylor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:46:58Z http://mathoverflow.net/feeds/user/987 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95247/polygons-that-are-hard-to-guard Polygons that are hard to guard Gray Taylor 2012-04-26T11:46:05Z 2012-04-26T22:49:15Z <p>Given an $n$-vertex polygonal 'art gallery' $P$ in the plane, it is possible to cover the interior of $P$ by placing 'guards' at (at worst) $\lfloor n/3\rfloor$ of the vertices of $P$. That this is sufficiently many can be shown elegantly by triangulating $P$, then $3$-colouring this triangulation and placing guards at the vertices with the least common colour. </p> <p>For a lower bound only a single family of examples is needed, and the standard is the $n$-pronged comb (or crown) which has $3n$ vertices and requires one guard for each prong. However, in considering variations on the art gallery problem it can be the case that the comb is easier to guard, and thus other families (which are harder in this new context) are required. So, is there (or can we construct in comments) a big list of 'hard to guard' polygons - that is, $n$-vertex polygons for which $\lfloor n/3 \rfloor$ guards are required - that could be used as starting points for considering variations?</p> http://mathoverflow.net/questions/54430/video-lectures-of-mathematics-courses-available-online-for-free/94393#94393 Answer by Gray Taylor for Video lectures of mathematics courses available online for free Gray Taylor 2012-04-18T11:53:49Z 2012-04-18T11:53:49Z <p><a href="https://www.coursera.org/category/math" rel="nofollow">Coursera</a> offers not just the videos, but entire courses: I'm currently following Probabilistic Graphical Models, which has weekly exercises and programming projects (which are marked by an autograder), plus community discussion boards and a wiki for collaborating with other students pursuing the course at the same time. Although you could presumably just create an account towards the end of term, archive off all the videos and then watch them at your leisure rather than trying to match the (reasonably demanding) schedule. </p> http://mathoverflow.net/questions/91692/need-there-be-infinitely-many-gaussian-primes-along-lines-that-contain-at-least-o Need there be infinitely many Gaussian primes along lines that contain at least one? Gray Taylor 2012-03-20T07:39:34Z 2012-03-20T11:22:04Z <p>Greetings from EuroCG 2012, from which I post via iPod, so apologies for lack of problem motivation, background research and mathematical formatting.</p> <p>Question:Suppose L is a horizontal or vertical line in the argand plane passing through a Gaussian prime. Are there infinitely many Gaussian primes on L?</p> <p>In fact, all I need is a next prime along a line, but of course if that was guaranteed one could repeat the process to keep going forever. Still, if there is a next prime, some idea of how far along it is might also be useful for the application in mind.</p> <p>Hopefully equivalent question for rational primes in rational integer sequences: let $s(k)=a^2+(b+k)^2$ for $k\ge0$. If $s(0)$ is prime, does the sequence $\{s(k)\}$ contain infinitely many primes?</p> http://mathoverflow.net/questions/77365/records-for-low-height-points-on-elliptic-curves-over-number-fields Records for low-height points on elliptic curves over number fields Gray Taylor 2011-10-06T15:22:18Z 2011-11-11T13:37:01Z <p>Elkies maintains <a href="http://www.math.harvard.edu/~elkies/low_height.html" rel="nofollow">a list of nontorsion points of low height on elliptic curves over Q</a>; does anyone know of anything similar for curves over number fields?</p> <p>Everest and Ward <a href="https://ueaeprints.uea.ac.uk/19694/" rel="nofollow">give examples</a> of points of height 0.01032... and 0.009721... on curves over Q(w) for w a cube root of unity or the golden ratio respectively. I have made a modest improvement in the latter case, recovering a point of height 0.009128... . </p> <p>In the context of the elliptic Lehmer problem the aim is to minimise dh(P) for d the degree of the number field, so working over quadratic extensions a point would have to have height less than 0.005 to be competitive with the examples in Elkies' table. Are there any examples?</p> http://mathoverflow.net/questions/77365/records-for-low-height-points-on-elliptic-curves-over-number-fields/80680#80680 Answer by Gray Taylor for Records for low-height points on elliptic curves over number fields Gray Taylor 2011-11-11T13:37:01Z 2011-11-11T13:37:01Z <p>Since no answers have been given here or via the NMBRTHRY mailing list (and as this question is now the top hit on google for 'low height points on elliptic curves'), perhaps you'll allow me the luxury of answering my own question... </p> <p>I have constructed a page detailing some points on curves over quadratic fields with height at most 0.01; two of the examples have height less than 0.005, so (scaling for degree) are competitive with some of those listed by Elkies. The table can be found <a href="http://maths.straylight.co.uk/low_height" rel="nofollow">here</a>, and additional contributions would be happily accepted! </p> http://mathoverflow.net/questions/1714/best-online-mathematics-videos/54687#54687 Answer by Gray Taylor for Best online mathematics videos? Gray Taylor 2011-02-07T19:40:42Z 2011-02-07T19:40:42Z <p>At the accessible end of the scale, <a href="http://www.youtube.com/user/Vihart" rel="nofollow">Vi Hart's</a> "doodling in math class" series and subsequent videos are a delight. </p> http://mathoverflow.net/questions/15664/what-is-the-best-graph-editor-to-use-in-your-articles/15690#15690 Answer by Gray Taylor for What is the best graph editor to use in your articles? Gray Taylor 2010-02-18T10:48:01Z 2010-02-18T10:48:01Z <p>I already had about 30 pages of graphs typeset with xymatrix for my thesis before discovering tikz; but was so impressed by it that I was happy to rewrite them all. As well as (imho) looking better, it gave me cross-platform compatibility - xypic seems to need pstricks, so on the mac with TeXshop (which uses pdflatex, I assume) the old graphs couldn't even be rendered. </p> <p>Its ability to construct graphs iteratively can also be a massive timesaver- for instance, I wanted a bunch of otherwise identical rectangles at various positions, so with tikz could just loop over a list of their first coordinate rather than having to tediously cut,paste and modify an appropriate number of copies of the command for a rectangle. Particularly handy when I then decided they all needed to be slightly wider!</p> <p>There's a gallery of tikz examples <a href="http://www.texample.net/tikz/examples/" rel="nofollow">here</a>, to give you some idea of what it's capable of (and with the relevant source code- I did find the manual a bit hard to understand and learnt mostly by examples or trial and error).</p> <p>The vector graphics package inkscape (which I used to use for drawing more complicated graphs for inclusion as eps images) also apparently has a plugin to export as tikz, although I haven't tried that out.</p> http://mathoverflow.net/questions/10911/english-reference-for-a-result-of-kronecker English reference for a result of Kronecker? Gray Taylor 2010-01-06T12:45:00Z 2010-02-01T01:42:36Z <p>Kronecker's paper <em>Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten</em> apparently proves the following result that I'd like to reference:</p> <blockquote> <p>Let $f$ be a monic polynomial with integer coefficients in $x$. If all roots of $f$ have absolute value at most 1, then $f$ is a product of cyclotomic polynomials and/or a power of $x$ (that is, all nonzero roots are roots of unity).</p> </blockquote> <p>However, I don't have access to this article, and even if I did my 19th century German skills are lacking; does anyone know a reference in English I could check for details of the proof?</p> http://mathoverflow.net/questions/6248/recovering-phin-from-a-multiple Recovering $\Phi(n)$ from a multiple? Gray Taylor 2009-11-20T10:34:23Z 2010-01-22T21:12:50Z <p>I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn't recall the reason for, nor original source of.</p> <p>Given an unfactored $n=pq$, computing $\phi(n)$ is as hard as finding $p,q$; this is the key idea of various "RSA-like" cryptosystems. One presented had a step in which for a secret $k$ and a random $t$, $k-t\phi(n)$ is transmitted. The claim was then that this process should only be applied once, as if an attacker sees $k-t\phi(n)$ and $k-u\phi(n)$ then they can recover $(t-u)\phi(n)$, and it's alleged that this makes it easier to compute $\phi(n)$. </p> <p>So my question is, why is it easier to compute $\phi(n)$ given a random multiple of it, assuming we're at "cryptographic size"? (that is, $p,q$ sufficiently large that it's not feasible to try and factor $n$ and $\phi(n)$)</p> http://mathoverflow.net/questions/12085/experimental-mathematics/12105#12105 Answer by Gray Taylor for Experimental Mathematics Gray Taylor 2010-01-17T15:20:35Z 2010-01-17T15:20:35Z <p>I was recently at <a href="http://www.fields.utoronto.ca/programs/scientific/09-10/FoCM/discovery/" rel="nofollow">this workshop</a> at Fields on 'discovery and experimentation in number theory': you can get audio and slides from many of the presentations <a href="http://www.fields.utoronto.ca/audio/#discovery" rel="nofollow">here</a> although the one I wanted to recommend - David Bailey's talk - appears to be audio only. It depends what you mean by 'major mathematical advance' but there certainly seem to be many problems in number theory where even if the proof doesn't depend on heavy computation, gaining insight into what to set about proving did. I personally logged several CPUweeks trying to get to grips with my own thesis topic.</p> http://mathoverflow.net/questions/6781/ade-type-dynkin-diagrams/6787#6787 Answer by Gray Taylor for ADE type Dynkin diagrams Gray Taylor 2009-11-25T11:24:24Z 2009-11-25T11:24:24Z <p>Let $G$ be a connected graph with the property that all eigenvalues of $G$ lie in $[-2,2]$ (such a $G$ is called cyclotomic). Then $G$ is either one of $\tilde{E}_6,\tilde{E}_7,\tilde{E}_8$, an $\tilde{A}_n$ for $n\ge 2$, a $\tilde{D}_n$ for $n\ge4$, or an induced subgraph of one of these. In other words, the ADE graphs classify the maximal cyclotomic graphs. </p> http://mathoverflow.net/questions/3939/when-is-a-monic-integer-polynomial-the-characteristic-polynomial-of-a-non-negativ/4253#4253 Answer by Gray Taylor for When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix? Gray Taylor 2009-11-05T13:20:33Z 2009-11-05T13:20:33Z <p>Second idea, which at least gives some necessary conditions...</p> <p>The <a href="http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius%5Ftheorem#Perron-Frobenius%5Ftheorem%5Ffor%5Fnon-negative%5Fmatrices" rel="nofollow">Perron-Frobenius Theorem for non-negative matrices</a> ensures that there is always a real eigenvalue equal to the spectral radius. So a polynomial cannot be the char.poly. of such a matrix if it has no real roots, or if the greatest absolute value of any root is greater than the largest real root. This necessary condition thus generalises your observation in the monic quadratic case.</p> http://mathoverflow.net/questions/3939/when-is-a-monic-integer-polynomial-the-characteristic-polynomial-of-a-non-negativ/3974#3974 Answer by Gray Taylor for When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix? Gray Taylor 2009-11-03T17:53:32Z 2009-11-03T17:53:32Z <p>I can possibly offer a counterexample, from <a href="http://arxiv.org/abs/0907.0371" rel="nofollow">here</a> .</p> <p>If P=x^7-8x^5+19x^3-12x+1 were the characteristic polynomial of a matrix corresponding to a graph, then it would be the char.poly of a matrix corresponding to a charged signed graph (symmetric, all entries 0,1 or -1). For such matrices we define the associated reciprocal polynomial to be (z^d)X(z+1/z), where X is the characteristic polynomial and d its degree. In this case, the associate reciprocal polynomial would be z^14-z^12+z^7-z^2+1. For any integer polynomial we can find a mahler measure, and the mahler measure of this polynomial is 1.20261... However, Smyth and McKee determined the Mahler measures less than 1.3 that arise from associated reciprocal polynomials of charged signed graphs, and this quantity is not attained. </p> <p>So P cannot be the characteristic polynomial of a charged signed graph, of which graphs are a special case. Does P satisfy your non-negativity conditions on the roots? The sums of odd powers seem to be zero.</p> http://mathoverflow.net/questions/2250/thematic-programs-for-2010-2011/2267#2267 Answer by Gray Taylor for Thematic Programs for 2010-2011? Gray Taylor 2009-10-24T09:26:46Z 2009-10-24T09:26:46Z <p>By next year do you mean the next academic year? If <em>not</em>, there's <a href="http://www.crm.umontreal.ca/NT2010/" rel="nofollow">Number Theory as Experimental and Applied Science</a> at CRM in Montreal Jan-Apr 2010. </p> http://mathoverflow.net/questions/1443/algorithm-to-find-all-the-cycle-bases-in-a-graph/1879#1879 Answer by Gray Taylor for Algorithm to Find all the Cycle Bases in a Graph Gray Taylor 2009-10-22T14:58:43Z 2009-10-22T14:58:43Z <p>By 'clean cycle' do you perhaps mean 'chordless cycle'? This I think is well-defined without an embedding, as it's just a condition on adjacency of vertices. If so, <a href="http://research.nii.ac.jp/~uno/code/cypath.htm" rel="nofollow">this page</a> seems to describe an algorithm for enumerating such cycles.</p> http://mathoverflow.net/questions/95247/polygons-that-are-hard-to-guard Comment by Gray Taylor Gray Taylor 2012-04-26T15:23:10Z 2012-04-26T15:23:10Z At the moment the variation I'm playing with is to allow guards to see through a single wall (the k=1 case of 'k-transmitters'), but to require that they be placed in the exterior of $P$. For the upper bound this is not much of a variation- if you can $0$-guard at $l$ vertices, you can $1$-guard at $l$ external locations by pushing the guards just outside. But for the lower bound I haven't yet drawn something that I couldn't get away with one less guard, since they can see into two prongs or spikes or fiddly bit I add. But I suspect this could just be inexperience on my part! http://mathoverflow.net/questions/77398/how-did-ores-conjecture-become-a-conjecture/77401#77401 Comment by Gray Taylor Gray Taylor 2011-10-07T16:48:16Z 2011-10-07T16:48:16Z I was about to post precisely this! Extra confusion is caused by there being another number-theoretic problem sometimes descibed as Lehmer's conjecture - the assertion that Ramanujan's tau function is nonzero - for which it's also not clear that he actually made the conjecture, rather than just suggesting the question. http://mathoverflow.net/questions/17730/whats-the-definition-of-saturated-subgraph Comment by Gray Taylor Gray Taylor 2010-03-10T14:44:27Z 2010-03-10T14:44:27Z For context, could you tell us which paper? http://mathoverflow.net/questions/12186/are-there-any-historical-accounts-of-individuals-who-study-math-books-like-novels Comment by Gray Taylor Gray Taylor 2010-01-18T13:08:13Z 2010-01-18T13:08:13Z Could one even learn a novel 'sufficiently well' by reading it 'like a novel'? Excluding those with phonebook-memorizing savant abilities, I don't think reading any book recreationally would be the same as studying it. http://mathoverflow.net/questions/10911/english-reference-for-a-result-of-kronecker/10915#10915 Comment by Gray Taylor Gray Taylor 2010-01-06T14:14:32Z 2010-01-06T14:14:32Z Thanks for the proofs both of you; I'm referencing the result in my thesis so yes, I need something to cite, but for something that admits quick proofs like this I feel I should definitely know <i>how</i> it works rather than just appeal to a source. http://mathoverflow.net/questions/3939/when-is-a-monic-integer-polynomial-the-characteristic-polynomial-of-a-non-negativ/3974#3974 Comment by Gray Taylor Gray Taylor 2009-11-03T18:33:08Z 2009-11-03T18:33:08Z Ah, I see. The basic mahler measure idea would work for multigraphs (as the only 'good' integer matrices are the ones corresponding to CSMs) but if you relax symmetry by introducing directionality I imagine things break.