Unsolved math problems?

K.J.Healey

Does anyone have a list of decent sites which include a range of either unsolved mathematical problems, or unproven formulae? There used to be on liked from my employer's mathematical index, but it is no longer there. I understand that the possibility of doing something like finding all the zeros of the riemann zeta function is impossible for most of the world's population(including me), but regardless, I am curious as to where the mathematics train consistently runs into the wall. I'm mostly interested in the history of theory that went unproven for a long time and what it took (both time and ingenius mathematical concepts) to solve or prove these theories.

Thanks.

mathwonk

here is some history on the famous and recently solved after 100 years, poincare conjecture.

Background on the problem, by John Milnor:

http://www.math.sunysb.edu/~jack/PREPRINTS/poi-04a.pdf

As a second step, see Milnor's next article on the progress towards
the conjecture & classifying three-manifolds:

http://www.math.sunysb.edu/~jack/PREPRINTS/tpc.pdf )

On the recent solution:

Speaker: Jason Parsley, University of Georgia
Title of talk: Introduction to the Poincare Conjecture

Abstract: In 1904, Poincare conjectured that every closed,
simply-connected three-dimensional manifold is homeomorphic to the
three-sphere. This problem remained unsolved for almost 100 years.
Recently, Perelman posted a couple of papers on the Ricci flow, an
equation of manifolds evolving based on their curvature, that implied
Poincare's conjecture was true.

In this talk, we will start by defining all relevant terms, then briefly
describe the history of the Poincare conjecture and mention analogs in
higher dimensions. We touch on Thurston's Geometrization Program, which
roughly says that there are exactly eight different types of geometries
that are possible for three-dimensional manifolds. If time allows, the
last few minutes will be devoted to how Hamilton and Perelman used
Riemannian Geometry to attack this problem.


*************************
R. Jason Parsley
VIGRE Postdoc
Department of Mathematics
University of Georgia
706.542.2562
*************************

fourier jr

i think you deify mathematicians/profs too much. but just as there are good & bad dishwashers/janitors/7-11 attendants, i guess there are good & bad mathematicians. they're like everyone else really, some just don't like to admit it.

anyway, the rest of the clay math problems (besides the poincare conjecture) here:
http://www.claymath.org/millennium/

other unsolved problems include the following:
a. the invariant-subspace problem (= whether there is a separable, infinite-dimensional banach space on which every linear operator has an invariant subspace. i think it's a natural generalization of a theorem that burnside proved but i can't remember what it was)
b. whether every finite group H occurs as the Galois group of a finite Galois extension of the field of rational numbers. shafarevich proved this for solvable H & others (like hilbert) proved other special cases but the general problem is still unsolved.

honestrosewater

mathworld lists several problems and links.

Alkatran

They give a bad example for an NP = P problem. They give the example of picking 100 students from a list of 400, but that certain pairs of students can't both be picked. Here's a polynomial time for that one:

1: Take input and create a list of the students alongside the students they are incompatible with.
IE if roger can't go with tom, and the list is roger, tom, and becky, we get:
Roger -> tom
tom -> roger
Becky

2: Create a variable N and set it to 0. Then loop step 3 while remainingstudents > 0 and acceptedstudents < requirement

3: Construct a loop which goes through the list of students adding them to the list

3a: For(int m = 0, remainingstudents > m && acceptedstudents < requirement, m++)
-For the non Java types, that means start m at 0, check if the conditions are met, and for every new iteration of the loop, increase m by 1.

3b: Check if the number of students disallowed by the current student is equal to n.
If it is then add the student to the accepted list and remove all the students disallowed by this student from the entrance list. (adjust m as necessary)

3c: end of loop

4: end of loop involving n

5: Return wether or not the number of accepted students is at least the amount of needed students



There. That will run in...

n goes from 0 to a maximum of the number of students - 1
m goes from 0 up to at most the number of students
in the worst case scenario, where everyone is paired with everyone, removing students from the list will take the ~number of students squared operations. But n and m would not be looped at all, but I will just say that there can be a squared time inside that loop.

Final time (overestimated) ~ O(x^4)
(n from 0 to x, m from 0 to x, removing from list is (0 to ~x, 0 to x))

The logic behind this is to add any student who is paired with very few students. By adding this student you are forcing the exit of another student who would force the exit of at least, if not more, students. This method should work for all inputs.

master_coda

I don't think your algorithm will actually work. It sounds like an algorithm that might find the correct solution, but might also fail when a solution exists.

Hurkyl

Ah, but the greedy algorithm doesn't always work!

Here's an example where we try to pick three students out of 7. Here's the list of unacceptable pairs:

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

So, for example, 14 means that 1 and 4 aren't compatable.

Now, here's the counts of how many students are incompatable with a selected student:

1 4
2 4
3 4
4 3
5 5
6 5
7 5

Here, the greedy pick is to first accept student #4. This means we cannot pick students 1, 2, or 3. Therefore, we must also accept two of the students numbered 5, 6, and 7, but they are all incompatable with each other!

The only solution here is to accept students 1, 2, and 3.

CrankFan

Nice points, but I think it's a little worse than that.

For simplicity let's call two students that can't be paired, enemies. If every student has at least 1 enemy this algorithm, as specified, fails to add any students to the accepted list.

In this case N (or is it n?) never changes; it stays at 0. In fact it doesn't appear that n/N changes even if a student is removed from the candidate list and added to the accepted list. However, it does look like there is some kind of general plan to increment n/N; but when or why? That's an important detail.

There's not much point to guessing what was intended since "obvious" choices of what was intended lead to incorrect algorithms as well.

fourier jr

check these out:
-- extend the mathematical model of general equilibrium theory to include price adjustments (introduce dymanics into economics)
-- is there a polynomial-time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax >= b?
-- can a zero of n polynomial equations in n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?
-- what are the limits of intelligence, both artificial and human?

those are from smale's article referenced in that mathworld page. there were 18 problems in total; some are on the clay list (navier-stokes equations, riemann hypothesis, poincare conjecture) & i don't really get the other ones

Alkatran

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67
Create list
1 - 4, 5, 6, 7
2 - 4, 5, 6, 7
3 - 4, 5, 6, 7
4 - 1, 2, 3
5 - 1, 2, 3, 6, 7
6 - 1, 2, 3, 5, 7
7 - 1, 2, 3, 5, 6

I see the problem now. They're blocking the same people! Well, I guess I got snookered. Damn. Hmmmm problem is interesting now!

I know the problem is apparently unsolveable, but there's nothing like an unsolveable problem to learn from. At least if I encounter this problem I have a "try it quick then try it hard" method

I'm thinking of perhaps only counting equal sets once. But that can be beaten by adding 8 and 9 as enemies of eah other, 1 and 2... Perhaps grouping similar sets together... to get 3 * the set / 4... But then we need to sort since it's not integer...

fourier jr

wikipedia has a bunch of conjectures & unsolved problems in math & comp sci:
http://en.wikipedia.org/wiki/Category:Conjectures
http://en.wikipedia.org/wiki/Unsolve...in_mathematics
http://en.wikipedia.org/wiki/List_of...mputer_science

gazzo

Check out your uni library. I saw a book yesterday on unsolved problems (twas yellow, by a Russian professor i think, or Italian), there are quite a few. Comes with commetary as well which is good! :D

Take care.