Final Project
CS 241 Spring 2021
April 2021
1 Cutting Edge Research
For this final project, you will work in groups of yourself and up to 2 otherstudents of your choosing (solo work is fine) to look into some interesting openproblem in the field of computer science or mathematics. For this problem Iwould like you to write
1. A background section detailing in simple terms the field and necessaryinformation to understand your results
2. A results section detailing in simple terms the prior proofs/experimentsperformed in the past
3. A summary section detailing potential consequences of a proof of thisproblem, and how it could impact a sector of computer science
These sections do not need to be long, as they are just so that I can suf-ficiently understand the following section. I do not have a minimum requiredlength, however note that if you have each of these sections as one single sen-tence such that it appears you have only a surface level understanding on thematerial, I will grade accordingly. These three sections will be worth 50% ofyour final exam grade, and will be graded on how well you describe the materialto me, as well as how well I believe you understand the material.
Next I ask that you take the results and document the process of you “play-ing” with the results. Most research is gained through insight into other’s cut-ting edge research, and through new perspectives that the original researchersdid not consider. Playing with the results can be, but are not limited to, any ofthe following
• Expanding on the results of a paper (better error bounds, consideringdifferent cases, etc.)
• Applying new research to a problem
• Using your class knowledge to look at a problem in a new way
• Applying techniques from another field to a problem
1
Numerically computing large amounts of examples will not begood enough this semester. For example if you are working on TwinPrimes you cannot ust calculate the first 100 twin primes.
This section will be also 50% of your final exam grade, and will consist ofhow well you articulate your thought process while attempting to expand onthe results of the paper. You can get negative results (ie the stuff you came upwith failed / is uninteresting) but so long as I can tell you made a clear attemptto attack the problem in a way you found interesting, and legitimately tried, Iwill consider that sufficient.
All research papers should be done in real life using LATEX, and while I cannotforce you to use Latex (without being an asshole at least) I can offer that if youwrite your research paper in Latex I will give it +5 extra credit points.
If your team has more than 1 member, each team member musthave their own section in the paper dedicated to their attempt toplay with the problem. If your team is attempting something very difficultand long, it will be fine to have several members work on the same section, butit should be challenging enough to warrant more than one person’s attempt.Only 1 background/results/summary section is needed per paper.
2 Potential Problems
In this section I will write out some problems that are simple enough for un-dergraduate students to understand (or in the case of the millenium problems,different formulations y’all might get)
2.1 Weak Sendov’s Conjecture
Field: Calculus, AnalysisSuppose we have a polynomial p(x) such that all the roots of the polynomial
p exist on the interval [−1, 1]. Let c ∈ [−1, 1] be a critical point of p, where acritical point is defined to be a point at which p′(c) = 0. Is it true that everycritical point of p is at least of distance 1 away from at least one root of p?
Formulating this in more mathy lingo. Let the set of roots and critical pointsbe defined as follows for some given polynomial p
R(p) = {x|p(x) = 0}C(p) = {x|p′(x) = 0}
(1)
where R(p) ⊂ [−1, 1]. ∀c ∈ C(p) does ∃x ∈ R(p) such that |c− x| ≤ 1?
2.2 Mersenne Primes
Any prime of the form 2k−1 is called a Mersenne Prime. For example, 25−1 =31 is a Mersenne Prime, but 24− 1 = 15 is not. Are there an infinite number ofMersenne Primes?
2
A necessary condition for 2k−1 to be prime is k needs to be prime, howeverthis is not sufficient (ex 211 − 1 is not prime).
2.3 Fermat Numbers
Define the Fermat numbers to be Fn = 22n
+1. Currently full factorizations areonly known for n ≤ 11 (complete info can be found here of all current statushttp://www.prothsearch.com/fermat.html).
What are the unknown prime factors of 2212+1 = 24096+1? Other problems
can be gathered from the page provided such as is F33 prime?
2.4 Twin Prime Conjecture
Field: Number TheoryWe call a pair of prime numbers that have a difference of two “twin primes”.
Examples of twin primes include
(3, 5), (5, 7), (11, 13), (17, 19), . . . . (2)
Are there an infinite number of twin prime pairs?Writing this out in a mathy way. Define the set of twin primes to be
T = {(p, p+ 2)|p, p+ 2 are prime}. (3)
Is |T | infinite?
2.5 Collatz Conjecture
Field: Number TheoryStart with any number n ∈ N and apply the following process: if n is
even, divide it by 2, if n is odd multiply by 3 and add 1. Repeat this processindefinitely. As an equation this would be if we start with the sequence terms0, s1, s2, . . . then we would say that
sn+1 =
{sn2 n even
3sn + 1 n odd. (4)
Will this process always eventually end up at 1 for any initial input?
2.6 P vs. NP and Polynomial Classification
The problem of P vs. NP is fairly famous in CS, so I’ll spare the details of it,but I will provide an interesting reformulation of the problem that uses calculusthat y’all might enjoy working on.
Given a polynomial p(~x) with ~x ∈ Rn, can you devise an algorithm that inpolynomial time will return true if ∃~x ∈ [0, 1]n (n-dimensional cube of length1), and false if otherwise?
3
p also has some special properties. First it is at most a trinomial, whichmeans that the sum of the powers of each term cannot be more than 3. Also,p is multilinear, which means that you cannot have any individual term be toa power higher than 1. For example, here are some acceptable terms of thepolynomial
x1x2x3, 5x1x4, −2×6, −x8x11x12 (5)
where these would be invalid terms for the polynomial
x21x2, x2x33x4, 5×25 (6)
Notice that this also means that for every 1 ≤ j ≤ n that ∂2p∂x2
j= 0. In case
you are still having trouble visualizing, in R3, every polynomial p would be ofthe form
p(~x) = c0 + c1x1 + c2x2 + c3x3 + c4x1x2 + c5x2x3 + c6x1x3 + c7x1x2x3 (7)
where ci ∈ R are arbitrary coefficients.It can be proven that the minima of p on the interval [0, 1]n must be on a
corner point (input where everything is either 0, 1), however as n increases, thenumber of corner points scales as 2n which makes checking each one unfeasible.
2.7 The Riemann Hypothesis and Robin’s Inequality
Again, the Riemann Hypothesis is super famous so I’ll spare the details, buthere is a fun reformulation that doesn’t require too much extra knowledge.
Choose some natural number n > 5040 and write it as its prime numberdecomposition: n = pk11 p
k22 . . . pkmm . Is the following inequality always true:
m∏j=1
pkj+1j − 1
pkjj (pj − 1)
≤ eγ log
log
m∏j=1
pkjj
(8)
where γ is the Euler-Mascheroni constant (≈ .577 . . .) and log is the naturallogarithm?
The following properties are true about this inequality for numbers > 5040
• Robin’s Inequality is true for every odd number
• If Robin’s Inequality is true for pk11 pk22 . . . pkmm , then it is true for
P k11 P k22 . . . P kmm where pj ≤ Pj
• Robin’s Inequality is true for any pk11 pk22 . . . pkmm if ∀kj < 5
• Robin’s Inequality is true if m < 4
• The left hand side is bounded, but the right hand side is not, so forsufficiently large prime products, all larger exponents are true.
Showing that Robin’s Inequality is true ∀n > 5040 is equivalent to solvingthe Riemann Hypothesis.
4
2.8 Irrationality of π + e
It is know that both π and e are irrational numbers, however it is still unknownif π + e is also irrational.
Question, can we find a a, b ∈ N where π + e = ab ?
2.9 Normality of π
You know how everyone says that since π is infinite you can find any sequenceof digits in it (like your phone number)? Well we actually don’t know if thisis true because we don’t know if π is a normal number. Normality means thatthe digits of π are truly randomly distributed and don’t depend on previousnumbers. We also know that normal numbers are uncountable so most are, butwe can’t find any
Is π normal?
2.10 Subarray Sum
Given a list of positive integers L and target number T , can you write analgorithm that runs in polynomial time and returns true if there exists a setof numbers in L that sum to T and false if no such set exists?
2.11 Polynomial Identity Testing
Given a n dimensional polynomial, can you write an algorithm that runs inpolynomial time that returns true if the polynomial is identically equal to 0and false if not?
2.12 MOBA Wave Management
See the extra document on Canvas
5
