Simple unsolved math problem, 4

Posted on 2016/11/23 by wdjoyner

Problem: Optimally pack n unit circles into the smallest possible equilateral triangle.

circle-packing_60_60_60_wikipedia

Let L(n) denote the length of the side of the smallest equilateral triangle in which n circles have been packed optimally. This number is, in general, unknown.

The minimum upset ranking problem

Posted on 2016/11/11 by wdjoyner

Suppose n teams play each other, and let Team $r_1 <$ Team $r_2 < \dots <$ Team $r_n$ denote some fixed ranking (where $r_1,\dots,r_n$ is some permutation of $1,\dots,n$ ). An upset occurs when a lower ranked team beats an upper ranked team. For each ranking, ${\bf r}$ , let $U({\bf r})$ denote the total number of upsets. The minimum upset problem is to find an “efficient” construction of a ranking for which $U({\bf r})$ is as small as possible.

In general, let $A_{ij}$ denote the number of times Team i beat team $j$ minus the number of times Team j beat Team i. We regard this matrix as the signed adjacency matrix of a digraph $\Gamma$ . Our goal is to find a Hamiltonian (undirected) path through the vertices of $\Gamma$ which goes the “wrong way” on as few edges as possible.

Construct the list of spanning trees of $\Gamma$ (regarded as an undirected graph).
Construct the sublist of Hamiltonian paths (from the spanning trees of maximum degree 2).
For each Hamiltonian path, compute the associated upset number: the total number of edges transversal in $\Gamma$ going the “right way” minus the total number going the “wrong way.”
Locate a Hamiltonian for which this upset number is as large as possible.

Use this sagemath/python code to compute such a Hamiltonian path.

def hamiltonian_paths(Gamma, signed_adjacency_matrix = []):
    """
    Returns a list of hamiltonian paths (spanning trees of 
    max degree <=2).

    EXAMPLES:
        sage: Gamma = graphs.GridGraph([3,3])
        sage: HP = hamiltonian_paths(Gamma)
        sage: len(HP)
        20
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: Gamma = Graph(A, format='weighted_adjacency_matrix')
        sage: HP = hamiltonian_paths(Gamma, signed_adjacency_matrix = A)
        sage: L = [sum(x[2]) for x in HP]; max(L)
        5
        sage: L.index(5)
        21
        sage: HP[21]                                 
        [Graph on 6 vertices,
         [0, 5, 2, 1, 3, 4],
         [-1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]]
        sage: L.count(5)
        1

    """
    ST = Gamma.spanning_trees()
    if signed_adjacency_matrix == []:
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #print L,ST.index(X), max(L)
                HP.append(X)
        return HP
    if signed_adjacency_matrix != []:
        A = signed_adjacency_matrix
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #VX = X.vertices()
                EX = X.edges()
		if EX[0][1] != EX[-1][1]:
                    ranking = X.shortest_path(EX[0][0],EX[-1][1])
		else:
		    ranking = X.shortest_path(EX[0][0],EX[-1][0])
		signature = [A[ranking[i]][ranking[j]] for i in range(len(ranking)-1) for j in range(i+1,len(ranking))]
                HP.append([X,ranking,signature])
        return HP

Wessell describes this method in a different way.

Construct a matrix, $M=(M_{ij})$ , with rows and columns indexed by the teams in some fixed order. The entry in the i-th row and the j-th column is defined by $m_{ij}= \left\{ \begin{array}{rr} 0,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ 1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.$
Reorder the rows (and corresponding columns) to in a basic win-loss order: the teams that won the most games go at the
top of $M$ , and those that lost the most at the bottom.
Randomly swap rows and their associated columns, each time checking if the
number of upsets has gone down or not from the previous time. If it has gone down, we keep
the swap that just happened, if not we switch the two rows and columns back and try again.

An implementaiton of this in Sagemath/python code is:

def minimum_upset_random(M,N=10):
    """
    EXAMPLES:
        sage: M = matrix(QQ,[
        [0 , 0 , 1  , 0 , 0 , 0 ],
        [1,   0 ,  0,  1,  1,   0  ],
        [0 , 1 ,  0 ,  1 , 1  , 0  ],
        [1 , 0 , 0,  0 ,  0 , 0  ],
        [1 , 0 , 0 , 1 , 0 , 0  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: minimum_upset_random(M)
        (
        [0 0 1 1 0 1]                    
        [1 0 0 1 0 1]                    
        [0 1 0 0 0 0]                    
        [0 0 1 0 0 0]                    
        [1 1 1 1 0 1]                    
        [0 0 1 1 0 0], [1, 2, 0, 3, 5, 4]
        )

    """
    n = len(M.rows())
    Sn = SymmetricGroup(n)
    M1 = M
    wins = sum([sum([M1[j][i] for i in range(j,6)]) for j in range(6)])
    g0 = Sn(1)
    for k in range(N):
        g = Sn.random_element()
        P = g.matrix()
        M0 = P*M1*P^(-1)
        if sum([sum([M0[j][i] for i in range(j,6)]) for j in range(6)])>wins:
            M1 = M0
            g0 = g*g0
    return M1,g0(range(n))

Simple unsolved math problem, 3

Posted on 2016/10/22 by wdjoyner

A perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself. For example, 1 + 2 + 3 = 6 implies 6 is a perfect number.

Unsolved Problem: Are there any odd perfect numbers?

The belief, by some, that there are none goes back over 500 years (wikipedia).

If you want to check out some recent research into this problem, see oddperfect.org.

b5527a1273f40d19e7fa821caa0208b9

(Another unsolved problem: Are there an infinite number of even perfect numbers?)

Simple unsolved math problem, 2

Posted on 2016/10/18 by wdjoyner

In 1911, Otto Toeplitz asked the following question.

Inscribed Square Problem: Does every plane simple closed curve contain all four vertices of some square?

This question, also known as the square peg problem or the Toeplitz’ conjecture, is still unsolved in general. (It is known in lots of special cases.)

Inscribed square, by Claudio Rocchini

Thanks to Mark Meyerson (“Equilateral triangles and continuous curves”,Fundamenta Mathematicae, 1980) and others, the analog for triangles is true. For any triangle T and Jordan curve C, there is a triangle similar to T and inscribed in C. (In particular, the triangle can be equilateral.) The survey page by Mark J. Nielsen has more information on this problem.

Added 2016-11-23: See also this recent post by T. Tao.

Added 2020-07-01: This has apparently been solved by Joshua Greene and Andrew Lobb! See their ArXiV paper (https://arxiv.org/abs/2005.09193).

Simple unsolved math problem, 1

Posted on 2016/10/16 by wdjoyner

In 1937 Lothar Collatz proposed the 3n+1 conjecture (known by a long list of aliases), is stated as follows.

First, we define the function $f$ on the set of positive integers:

If the number $n$ is even, divide it by two: $f(n)=n/2$ .
If the number $n$ is odd, triple it and add one: $f(n)=3n+1$ .

In modular arithmetic notation, define the function $f$ as follows:
$f(n)= {n/2},\ if \ n\equiv 0 \pmod 2$ , and $f(n)= {3n+1},\ if \ n\equiv 1 \pmod 2$ . Believe it or not, this is the restriction to the positive integers of the complex-valued map $(2+7z-(2+5z)\cos(\pi z))/4$ .

The 3n+1 conjecture is: The sequence
$n,\ f(n),\ f^2(n)=f(f(n)),\ f^3(n)=f(f^2(n)),\ \dots$
will eventually reach the number 1, regardless of which positive integer $n$ is chosen initially.

This is still unsolved, though a lot of people have worked on it. For a recent survey of results, see the paper by Chamberland.

From xkdc by Randall Munroe – https://xkcd.com/710/

Problem of the week, 161

Posted on 2016/09/24 by wdjoyner

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

The residue of an integer n modulo an integer d > 1 is the remainder r left when n is divided by d. That is, if n = dq + r for integers q and r with 0 < r < d, we write $r \equiv n \pmod d$ for the residue of n modulo d. Show that the residue modulo 7 of a (large) integer n can be found by separating the integer into 3-digit blocks $n = b(s)b(s-1)\dots b(1)$ .(Note that b(s) may have 1, 2, or 3 digits, but every other block must have exactly three digits.) Then the residue modulo 7 of n is the same as the residue modulo 7 of $b(1) - b(2) + b(3) - b(4) + \dots \pm b(s)$ . For example,
$n = 25,379,885,124,961,154,398,521,655 \pmod 7$
$\equiv 655 - 521 + 398 - 154 + 961 - 124 + 885 - 379 + 25 \pmod 7$ $\equiv 1746 \pmod 7$ $\equiv 746 - 1 \pmod 7$ $\equiv 745 \pmod 7 \equiv 3 \pmod 7$ .
Explain why this works and show that the same trick works for residues modulo 13.

Problem of the week, 137

Posted on 2016/09/18 by wdjoyner

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

Problem of the week, 148

Posted on 2016/09/17 by wdjoyner

Suppose p and q are each monic polynomials of degree 4 with real coefficients and the intersection of their graphs is {(1, 3), (5, 21)}. If p(3) – q(3) = 20, what is the area enclosed by their graphs?

Problem of the week, 150

Posted on 2016/09/17 by wdjoyner

Let a, b, and c be real numbers and let f and g be real valued functions of a real variable such that $\lim_{x\to a} g(x) = b$ and $\lim_{x\to b} f(x) = c$ .
a. Give an example in which $\lim_{x\to a} f(g(x)) \not= c$ .
b. Give an additional condition on f alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$ .
c. Give an additional condition on g alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$ .

Real world applications of representation theory

Posted on 2016/08/06 by wdjoyner

(Subtitle: Representation theorists will rule the world one day just you wait)

This post describes some applications of representation theory of non-abelian groups to various fields and gives some references.

Engineering.
- Tensegrity – the design of “strut-and-cable” constructions.Want to build a building with cables and struts but don’t know representation theory? Check out these references:
  - R. Connelly and A. Back, “Mathematics and tensegrity”, Amer Scientist, April-May 1998, pages 142-151
  - symmetric tensegrities
- Telephone network designs.This is the information age with more and more telephone lines needed every day. Want to reach out and touch someone? You need representation theory.
  - F. Bien, “Construction of telephone networks by group representations”, Notices A. M. S. 36(1989)5-22
- Nonlinear network problems.This is cheating a little since the works in the reference below really use the theory of Lie groups instead of representation theory itself. Still, there is a tangential relation at least between representation theory of Lie groups and the solution to certain nonlinear network problems.
  - C. Desoer, R. Brockett, J. Wood, R. Hirshorn,
    A. Willsky, G. Blankenship, Applications of Lie group theory to nonlinear network problems, (Supplement to IEEE Symposium on Circuit Theory, 1974), Western Periodicals Co., N. Hollywood, CA, 1974
- Control theory.
  - R. W. Brockett, “Lie theory and control systems defined on spheres”, SIAM J on Applied Math 25(1973) 213-225
- Robotics.The future is not in plastics (see the movie “The Graduate“) but in robotics.
  How do you figure out their movements before building them? You guessed it, using representation theory.
  - G. Chirikjian, “Determination and synthesis of discretely actuated manipulator workspaces using harmonic analysis”, in Advances in Robotic Kinematics, 5, 1996, Springer-Verlag
  - G. Chirikjian and I. Ebert-Uphoff, “Discretely actuated manipulator workspace generation by closed-form convolution”, in ASME Design Engineering Technical Conference, August 18-22 1996
- Radar design.W. Schempp, Harmonic analysis on the Heisenberg nilpotent Lie group, with
  applications to signal theory, Longman Scientific & Technical, New York (Copublished in the U.S. with Wiley), 1986.
- Antenna design.B. Hassibi, B. Hochwald, A. Shokrollahi, W. Sweldens, “Representation theory for high-rate multiple antenna code design,” 2000 preprint (see A. Shokrollahi’s site for similar works).
- Design of stereo systems.We’re talkin’ quadrophonic state-of-the-art.
  - K. Hannabus, “Sound and symmetry”, Math. Intelligencer, 19, Fall 1997, pages 16-20
- Coding theory. Interesting progress in coding theory has been made using group theory and representation theory. Here are a few selected references.
  - F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes,
    North-Holland/Elsevier, 1993 (8th printing)
  - I. Blake and R. Mullin, Mathematical Theory of Coding, Academic Press, 1975
    49(1995)215-223
  - J.-P. Tillich and G. Zemor,
    “Optimal cycle codes constructed from Ramanujan graphs,” SIAM J on Disc. Math. 10(1997)447-459
  - H. Ward and J. Wood, “Characters and the equivalence of codes,” J. Combin. Theory A 73348-352
  - J. Lafferty and D. Rockmore, “Spectral Techniques for Expander Codes” , (Extended Abstract) 1997 Symposium on Theory of Computation (available
    at Dan Rockmore’s web page)
Mathematical physics.
Any complete list of books and papers in this field which use representation theory would be much too long for the limited goal we have here (which is simply
to list some real-world applications). A small selection is given below.
- Differential equations (such as the heat equation, Schrodinger wave equation, etc).M. Craddock, “The symmetry groups of linear partial differential equations
  and representation theory, I” J. Diff. Equations 116(1995)202-247
- Mechanics.
  - D.H. Sattinger, O.L. Weaver, Lie Groups and Algebras With Applications to Physics, Geometry, and Mechanics (Applied Mathematical Sciences, Vol 61) , Springer Verlag, 1986
  - Johan Belinfante, “Lie algebras and inhomogeneous simple materials”,
    SIAM J on Applied Math 25(1973)260-268
- Models for elementary particles.
  - Howard Georgi, Lie Algebras in Particle Physics, Addison-Wesley, 1995
  - J. Baez, “This week’s finds in mathematical physics – week 119,” posted to sci.math.research on 4-13-1998
- Quantum mechanics.
  - Eugene Wigner, “Reduction of direct products and restriction of representations to subgroups: the everyday tasks of the quantum theorists”, SIAM J on Applied Math 25(1973) 169-185
  - V. Vladimirov, I. Volovich, and E. Zelenov, “Spectral theory in p-adic quantum mechanics and representation theory,” Soviet Math. Doklady 41(1990)40-44
- p-adic string theory.
  - Y. Manin, “Reflections on arithmetical physics,” in Conformal invariance and string theory, Academic Press, 1989, pages 293-303
  - V. Vladimirov, I. Volovich, and E. Zelenov, p-adic analysis and mathematical physics, World Scientific, 1994
  - V. Vladimirov, “On the Freund-Witten adelic formula for Veneziano amplitudes,” Letters in Math. Physics 27(1993)123-131
Mathematical chemistry.
- Spectroscopy.B. Judd, “Lie groups in Atomic and molecular spectroscopy”, SIAM J on Applied Math 25(1973) 186-192
- Crystallography.
  - G. Ramachandran and R. Srinivasan, Fourier methods in crystallography,
    New York, Wiley-Interscience, 1970.
  - T. Janssen, Crystallographic groups, North-Holland Pub., London, 1973.
  - J. Zak, A. Casher, M. Gluck, Y. Gur, The irreducible representations of space groups, W. A. Benjamin, Inc., New York, 1969.
- Molecular strucure of the Buckyball.
  - F. Chung and S. Sternberg, “Mathematics and the buckyball”, American Scientist 83(1993)56-71
  - F. Chung, B. Kostant, and S. Sternberg, “Groups and the buckyball”, in Lie theory and geometry, (ed. J.-L. Brylinski et al), Birkhauser, 1994
  - G. James, “The representation theory for the Buckminsterfullerene,” J. Alg. 167(1994)803-820
Knot theory (which, in turn, has applications to modeling DNA) uses representation theory. F. Constantinescu and F. Toppan, “On the linearized Artin braid representation,” J. Knot Theory and its Ramifications, 2(1993)
The Riemann hypothesis.
Think you’re going to solve the Riemann hypothesis without using
representation theory? Check this paper out: A. Connes, “Formule de traces en geometrie non-commutative et hypothese de Riemann”, C. R. Acad. Sci. Paris 323 (1996)1231-1236. (For those who argue that this is not a real-world application, we refer to Barry Cipra’s article, “Prime Formula Weds Number Theory and Quantum Physics,” Science, 1996 December 20, 274, no. 5295, page 2014, in Research News.)
Circuit design, statistics, signal processing, …
See the survey paper
D. Rockmore, “Some applications of generalized FFTs” in Proceedings of the DIMACS
Workshop on Groups and Computation, June 7-10, 1995 eds. L. Finkelstein and W. Kantor, (1997) 329–369. (available at Dan Rockmore’s web page)
Vision – See the survey papers by Jacek Turski:Geometric Fourier Analysis of the Conformal Camera for Active Vision, SIAM Review, Volume 46 Issue 2 pages 230-255, 2004 Society for Industrial and Applied Mathematics, and, Geometric Fourier Analysis for Computational Vision, JFAA 11, 1-23, 2005.

Yet Another Mathblog

Category Archives: teaching mathematics