User gray taylor - MathOverflow

Polygons that are hard to guard

2012-04-26T11:46:05Z

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.

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?

Answer by Gray Taylor for Video lectures of mathematics courses available online for free

2012-04-18T11:53:49Z

Coursera 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.

Need there be infinitely many Gaussian primes along lines that contain at least one?

2012-03-20T07:39:34Z

Greetings from EuroCG 2012, from which I post via iPod, so apologies for lack of problem motivation, background research and mathematical formatting.

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?

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.

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?

Records for low-height points on elliptic curves over number fields

2011-10-06T15:22:18Z

Elkies maintains a list of nontorsion points of low height on elliptic curves over Q; does anyone know of anything similar for curves over number fields?

Everest and Ward give examples 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... .

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?

Answer by Gray Taylor for Records for low-height points on elliptic curves over number fields

2011-11-11T13:37:01Z

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...

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 here, and additional contributions would be happily accepted!

Answer by Gray Taylor for Best online mathematics videos?

2011-02-07T19:40:42Z

At the accessible end of the scale, Vi Hart's "doodling in math class" series and subsequent videos are a delight.

Answer by Gray Taylor for What is the best graph editor to use in your articles?

2010-02-18T10:48:01Z

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.

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!

There's a gallery of tikz examples here, 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).

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.

English reference for a result of Kronecker?

2010-01-06T12:45:00Z

Kronecker's paper Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten apparently proves the following result that I'd like to reference:

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).

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?

Recovering $\Phi(n)$ from a multiple?

2009-11-20T10:34:23Z

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.

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)$.

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)$)

Answer by Gray Taylor for Experimental Mathematics

2010-01-17T15:20:35Z

I was recently at this workshop at Fields on 'discovery and experimentation in number theory': you can get audio and slides from many of the presentations here 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.

Answer by Gray Taylor for ADE type Dynkin diagrams

2009-11-25T11:24:24Z

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.

Answer by Gray Taylor for When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix?

2009-11-05T13:20:33Z

Second idea, which at least gives some necessary conditions...

The Perron-Frobenius Theorem for non-negative matrices 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.

Answer by Gray Taylor for When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix?

2009-11-03T17:53:32Z

I can possibly offer a counterexample, from here .

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.

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.

Answer by Gray Taylor for Thematic Programs for 2010-2011?

2009-10-24T09:26:46Z

By next year do you mean the next academic year? If not, there's Number Theory as Experimental and Applied Science at CRM in Montreal Jan-Apr 2010.

Answer by Gray Taylor for Algorithm to Find all the Cycle Bases in a Graph

2009-10-22T14:58:43Z

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, this page seems to describe an algorithm for enumerating such cycles.

Comment by Gray Taylor

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!

Comment by Gray Taylor

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.

Comment by Gray Taylor

2010-03-10T14:44:27Z

For context, could you tell us which paper?

Comment by Gray Taylor

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.

Comment by Gray Taylor

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 how it works rather than just appeal to a source.

Comment by Gray Taylor

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.