Wikipedia:Reference desk/Archives/Mathematics/2013 January 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 17

Riemann hypothesis for curves over finite fields

Can anyone explain the Riemann hypothesis for curves over finite fields in a way that can be understood by someone who has not done any form of university standard math?

All I understand from the article is that for any curve that doesn't cross itself in a finite field, its roots are a number raised to the power of a half and this number has a modulus/size of F. The curve must be generated by a polynomial of degree 2g.

What is a genus? And is this on a projective plane or a Euclidean Plane? Is it on the Reimann sphere?

The answer to your question of whether someone can explain this to someone who doesn't know any mathematics is probably "No". I will try to highlight some of the things that you need to understand. First, this is not just about planar curves, but curves in any dimension. The general concept is that of an abstract algebraic curve, which relies on scheme theory. Intuitively, the genus of a curve is the number of holes in the curve. For instance, the Riemann sphere has genus zero, an elliptic curve has genus 1, and so forth. However, this intuition is not valid for curves over finite fields since such curves have only finitely many points, so the notion of "holes" does not make sense. To define the genus requires an understanding of sheaf cohomology. Now, if you have a curve over the algebraic closure of a finite field of characteristic p, then you can make sense of the number of points that curve has for values of $q=p^{n}=|F|$. The local Riemann hypothesis is an assertion about the zeros of the local zeta function, which is the generating function for the number of zeros of a given curve. Sławomir Biały (talk) 14:15, 17 January 2013 (UTC)

So the reimann zeta function for curves over finite fields is basically a function that gives you the zeros of the curve and, for a prime field of size q, when Z(q^-s)=0 (where Z is the local zeta function), the hypothesis was that Re(s)=1/2. Is this correct?

Close. The zeta function of a curve is essentially the generating function of the number of zeros of the curve over the various subfields of the algebraic closure. You're correct about the conclusion otherwise. Sławomir Biały (talk) 02:38, 19 January 2013 (UTC)

Here's my attempt to answer. You look at your curve defined over a finite field of q elements $\mathbb {F} _{q}$; this is given by a set of simultaneous polynomial equations (you need to work in projective space however to have all the required points at infinity).

There are a few conditions this has to satisfy, which I can state as the fact that if you take these polynomial equations, but instead of looking at solutions in the finite field, you look at solutions with complex numbers, the set of solutions is a (connected) Riemann surface. In particular, it has an underlying topological structure which is just a sphere (then the Riemann surface is the Riemann sphere), a torus (a donut shaped space, the corresponding Riemann surface is an elliptic curve), two-holed torus, etc. The number of holes is called the genus, which I'll denote g.

In any case, once you have this curve, you can put together the number of points $N_{n}$ it has over each finite field $\mathbb {F} _{q^{n}}$, of qⁿ elements, together into one function, its zeta function $Z(s)=\exp \left(\sum _{n=1}^{\infty }{\frac {N_{n}}{n}}(q^{-s})^{n}\right)$.

This might look a bit unmotivated, but there are good reasons coming from understanding characteristic polynomials and the Lefschetz fixed point theorem.

The zeta function will always have the form $Z(s)={\frac {P(q^{-s})}{(1-q^{-s})(1-q^{2}q^{-s})}}$ (this is part of the Weil conjectures for this simple case), where P is a polynomial of degree 2 g, for g the genus of the curve (the reason for this is rather deep, coming from étale cohomology).

The Riemann hypothesis in this case is then is that this polynomial $P(q^{-s})$ only has zeroes for s of real part 1/2. In fact it tells you a bit more about these zeroes (they are so called Weil numbers of weight 1), but that's not so important right now.

Hopefully this gives you an idea of what this is about. -Sam^Talk 08:32, 19 January 2013 (UTC)

Thank you Sam! I think I understand!! But how do you know which Riemann surface to use? Or does it not matter as long as the polynomial is of degree 2g? Also is $P(q^{-s})$ just $q^{s}$ substituted into the polynomial or is it another function of $q^{s}$?

The Riemann hypothesis for curves here is a separate statement for each possible curve you imagine, as opposed to the usual Riemann hypothesis, about the Riemann zeta function, which is a single statement.

So for any curve you choose, such as the projective line (the Riemann sphere) or an elliptic curve (a genus 1 Riemann surface), etc, you get a corresponding Riemann hypothesis which is a property about the zeroes of its zeta function. As each curve has its own zeta function, you get many different statements.

And yes, $P(q^{-s})$ is just what you said.

Hope that helps. --Sam^Talk 18:36, 19 January 2013 (UTC)

algebra word problems

1. Liam invested some money at 7% simple interest and twice as much at twice the rate elsewhere.If the simple interest income from the two funds totaled 1406.30 then how much was invested in each fund?

2. How many liters of 10% acid solution must be mixed with 5 liters of a 25% acid solution to give 15% solution?

3. The perimeter of a rectangle is 72 meters. If the width is 8 meters less than the length than what is the width of the rectangle?

4. Carl drove for 3 hours on a two lane state road she then increased her speed by 25 miles per hour on the freeway and drove for 6 more hours if the total trip was 510 miles then what was her speed on the freeway? — Preceding unsigned comment added by 108.223.170.235 (talk) 01:28, 17 January 2013 (UTC)

This is clearly homework, and we won't do it for you. What we will do is help you, if you first show us what you've done so far. StuRat (talk) 01:41, 17 January 2013 (UTC)

Undecidability of the Collatz conjecture

The article states that "a natural generalization of the Collatz problem is algorithmically undecidable". Wouldn't this imply that we can never find a counter example to the conjecture? Which would mean that the conjecture was true and we couldn't call it undecidable. Is there a name for this paradox and how is it resolved? 70.162.4.242 (talk) 08:24, 17 January 2013 (UTC)

Unfortunately, the word undecidable is used in two quite different ways, but closely enough related that it's easy to get them confused. You seem to be thinking of it in the sense of "can neither be proved nor disproved" (presumably, from some specific set of axioms). However, what Janos Simon seems to be talking about is undecidability in the sense of a decision problem — given some "Collatz-like" function, what is the answer to the corresponding question for that function? What he asserts is that there is no fixed algorithm that can correctly decide the answer to that question in all cases. That does not necessarily imply that any particular Collatz-like question is "undecidable" in the sense you seem to have in mind. --Trovatore (talk) 08:48, 17 January 2013 (UTC)

And I hesitate to bring it up, but it is even more complicated than that. Simon asserts that a version of the question is Π₂-complete, which may well imply that, for any given arithmetically sound finite set of axioms, there is some instance of the generalized problem not decide by that axiom set — I'd have to think about it to be sure. But I recommend that you not dwell on that point yet — first make sure you understand the difference between the two senses of the word, and then you'll have a better chance of learning about particular cases where one sense might imply the other, without confusing them. --Trovatore (talk) 08:53, 17 January 2013 (UTC)

I don't think the issue is the two meanings of "undecidable": if A is any undecidable arithmetic set, consider the algorithm which, on input n, enumerates all proofs in PA until it finds one settling the membership of n. Since A is undecidable, this must be partial, so there is some number n such that "$n\in A$" is undecidable from PA. Hence Simon's meaning implies the OP's meaning.

I think the answer to the OPs question is two-fold: first, "undecidable from PA implies true" only holds for $\Pi _{1}$ sentences, while the Collatz conjecture is $\Pi _{2}$; second, the proof of undecidability is carried out in a stronger axiom system, so even for $\Pi _{1}$ sentences, the sentence only becomes a theorem of the stronger system.--149.148.254.128 (talk) 10:36, 17 January 2013 (UTC)

If your A is supposed to denote the “natural generalization of the Collatz problem” from the reference, then the Collatz conjecture is the statement $42\in A$ (where 42 denotes the Gödel number encoding the original Collatz function, whatever that number actually is). Your argument does not say anything about provability of this statement in PA (or in any other formal system, for that matter), but about provability of some irrelevant statement with another n. The generalized computational problem does not correspond to any “generalized conjecture”, we can prove easily there are plenty of functions violating such a “conjecture” (that’s why the problem can be undecidable in the first place, as the set of all integers is trivially decidable).—Emil J. 12:32, 17 January 2013 (UTC)

Yes, I'm saying that there is a Collatz-like function such that PA does not decide whether or not the Collatz conjecture holds for this function in place of the standard one. I thought that was clear from context. And the OP was asking why this is not a paradox, which is what I addressed.--149.148.254.128 (talk) 14:25, 17 January 2013 (UTC)

I still think the basic confusion on the OP's part is between the two senses of the word "undecidable". That's why I hesitated to mention this other stuff. Note that, while the undecidability of the decision problem does imply that there is some instance of the problem that is not decided by PA, it does not in itself imply that any particular instance is not decided by PA. --Trovatore (talk) 18:19, 17 January 2013 (UTC)

Yes, I also think that confusion of the two meanings of “undecidable” is the main problem here.—Emil J. 18:42, 17 January 2013 (UTC)

What is radius of equilateral polygon?

What's the formula for calculating the radius of an equilateral and equiangular polygon (let's say a hexagon) if I know the length of one side? --71.189.190.62 (talk) 19:21, 17 January 2013 (UTC)

The polygon itself doesn't have a radius, only circular objects do. The inscribed circle and circumscribed circle have radii, however. Are you asking about the distance from the center to a vertex (the radius of the circumscribed circle), or from the center to the middle of one of the edges (the radius of the inscribed circle) ? StuRat (talk) 19:22, 17 January 2013 (UTC)

Anyway, formulas linking these three lengths are given in Regular polygon#Circumradius.—Emil J. 19:33, 17 January 2013 (UTC)

Well, yes, a polygon doesn't have a radius. Anyway, it has a diameter (see #Generalizations section), being the maximum distance between its vertices. The diameter of regular n–gon with side s and circumradius $r={\frac {s}{2\sin {\tfrac {\pi }{n}}}}$ equals

$d={\begin{cases}2r&\mathrm {for\ } n\mathrm {\ even\ } \geq 4\\2r\cos {\tfrac {\pi }{2n}}={\frac {s}{2\sin {\frac {\pi }{2n}}}}&\mathrm {for\ } n\mathrm {\ odd\ } \geq 3\end{cases}}$

CiaPan (talk) 12:56, 18 January 2013 (UTC)