Dan Christensen
10,115 followers -
Interested in math, physics, computation and more.
Interested in math, physics, computation and more.

10,115 followers
Dan's posts
Post has attachment
Game theory and partial orders

This post announces a paper that disproves a longstanding conjecture in game theory and also computes a 138 digit number related to partially ordered sets.

Let n be a natural number, and consider the following two-player game, called Subset Takeaway. The players take turns naming a non-empty proper subset of {1, ..., n} that doesn't contain any set named earlier. If a player has no legal move, they lose. For example, when n = 2, the second player will always win, since if the first player names {1}, the second player will name {2}, and vice versa. For n = 3, the second player can win by naming the complement of what the first player names, leading to a position equivalent to the n = 2 starting position. In 1981, Gale and Neyman showed that the same is true for n = 4 and n = 5, and conjectured that this pattern continues. In 1995, Mark Tilford and I showed it is true for n = 6, using a computer.

Andries Brouwer and I showed that for n = 7, the conjecture is false. This was checked by two independently written programs.

In addition, we realized that our techniques were exactly what is needed to make the following computation. Write P(n) for the set of all subsets of the set {1, ..., n}, a partially ordered set under inclusion. Count the number of total orders on P(n) which are compatible with the partial order. The answer was known for n ≤ 6, and we were able to compute it for n = 7, resulting in the 138 digit number shown in the last line below.

0 1
1 1
2 2
3 48
4 1680384
5 14807804035657359360
6 141377911697227887117195970316200795630205476957716480
7 630470261306055898099742878692134361829979979674711225065761605059425237453564989302659882866111738567871048772795838071474370002961694720

All of this is described in

Counterexamples to conjectures about Subset Takeaway and counting linear extensions of a Boolean lattice
Andries E. Brouwer, J. Daniel Christensen
https://arxiv.org/abs/1702.03018

#arXiv arXiv:1702.03018

﻿
Post has shared content
wrote an entertaining description of the functional exponential and logarithm of power series under composition, and gave concise Haskell implementations.

I'm reminded of Pierre Cartier's Mathemagics paper, which starts with exponentials and leads to the time ordered exponential from mathematical physics. It's available here:

http://www.emis.de/journals/SLC/wpapers/s44cartier1.pdf﻿
I eventually figured out how to exactly compute, and implement in Haskell, the "functional" logarithm and exponential of (some) formal power series. So, for example, we can get the formal power series for arcsin as exp(-log(sin)) where log and exp here are the functional versions.

In fact, exp here is just the exponential map from differential geometry, and log is its inverse.

I wrote it up here: http://blog.sigfpe.com/2017/02/logarithms-and-exponentials-of-functions.html﻿
Post has attachment
With the latest tools, it's now possible to change the mouth and facial expression of a person in real time, and to edit audio to completely change what a person is saying. For the facial expression, the new facial expressions are taken from an actor, and for the voice changes, you can simply type the words you want the person to say. Watch out for very realistic fake news.

https://mathbabe.org/2016/12/23/creepy-tech-that-will-turbocharge-fake-news/﻿
Post has shared content
This is going to be a fun event! I'm looking forward to being there.﻿
Learn advanced math at a ski resort - for free!

Homotopy type theory takes modern ideas on logic, computation, topology and category theory and weaves them into an elegant new set of axioms for mathematics, in which spaces replace sets.  In this brave new world, things like 'the space of all loops in a space' become just as simple and fundamental as the number 2.

On June 4-10, 2017, the American Mathematical Society will run a workshop on Homotopy Type Theory at the Snowbird Resort in Utah.

The goal is to bring together advanced graduate students and postdocs with some background in one or more areas such as algebraic topology, category theory, mathematical logic, or computer science, with the goal of learning how these areas come together in homotopy type theory, and working together to prove new results.  You'll need basic knowledge of just one of these areas to be a successful participant.

For more information, including the list of sample topics that participants may be working on and info on how to register, go here:

http://www.ams.org/programs/research-communities/2017MRC-1

Everyone is accepted into the program will receive financial support (room and board at the Snowbird Resort and up to \$650 towards airfare).  The application deadline is March 1st, 2017,  but it's better if  you register as soon as possible.

Most of the positions will be allocated to U.S. citizens and people at U.S. institutions, but a smaller number will be open to international participants.

If you have any questions, please feel free to contact any of the organizers: , , , , and .

﻿
Post has shared content
Post has shared content
The linked page gives an excellent description of the problem and the techniques that were used to come up with an optimal solution, with links to lots of further reading, an interactive map, and the raw data. ﻿
Post has attachment
Here's a question I asked yesterday on mathoverflow: is there a smooth functional F which determines whether a function f has a zero.

More precisely, does there exist a functional F that takes non-negative smooth (C-infinity) functions on the reals R as input, and produces a real number, with the following properties:

1) F(f) = 0 if and only if f has a zero on [0,1]

2) F is smooth in the sense that for any smooth non-negative function f(x,t) of two variables, if F is applied to f in the x variable, the resulting function of t is smooth.

Better formatting of the question can be found at the link:

http://mathoverflow.net/questions/251913/smooth-functional-to-detect-whether-a-function-has-a-zero﻿
Post has shared content
This should be a lot of fun!﻿
Next June,  ,  ,   and  are running a workshop on homotopy type theory as one of the AMS’s Mathematical Research Communities!

The goal of this workshop is to bring together advanced graduate students and postdocs having some background in one (or more) areas such as algebraic topology, category theory, mathematical logic, or computer science, with the goal of learning how these areas come together in homotopy type theory, and working together to prove new results. Basic knowledge of just one of these areas will be sufficient to be a successful participant.

https://golem.ph.utexas.edu/category/2016/10/mathematics_research_community.html﻿
Post has shared content
While the linked post uses the typography of Bladerunner as motivation, it is full of interesting facts about the movie.﻿
"The Immortal Game [that Tyrell and J.F. are playing in Blade Runner] is notable in that Anderssen defeated Kieseritzky despite sacrificing a bishop, both rooks, and his queen. By the time Batty meets Tyrell, he has already sacrificed Leon, Zhora, and two other Replicants in his quest to meet his maker."

The typographical exegesis at https://typesetinthefuture.com/2016/06/19/bladerunner/
of Blade Runner is amazing in its detail. Below is the relevant part of the game, in an animated gif. It took me a while to work out the chess set used. (via bb)﻿
Post has shared content
As another followup on the HoTT Toronto workshop, all the videos are now posted online! Given the amount of chalkboard work, the low resolution is a bit of a shame (though still readable). But nonethless, the sound quality is very clear and professional, as is the videography.

http://www.fields.utoronto.ca/video-archive/event/2012﻿