The most recent take from the Bureau of Labor Statistics says the participation rate of all US workers is 63.6 percent of the population - the lowest figure since Dolly Parton sang "9 to 5" in December 1981.
The most recent take from the Bureau of Labor Statistics says the participation rate of all US workers is 63.6 percent of the population - the lowest figure since Dolly Parton sang "9 to 5" in December 1981.
Burns : journal of the International Society for Burn Injuries , Vol. 36, No. 3. , pp.
I started reading Matousek’s discrete geometry book. Specifically, chapter 12 on applications of high-dimensional polytopes. Mostly because he apparently draws a connection between graphs and the Brunn-Minkowski theory, and I’m interested to see exactly what that connection is and if it has any interesting implications.
I just finished the proof of the weak perfect graph conjecture (it’s been a while since I read a nontrivial pure math proof, so I haven’t actually *digested* it entirely). Now I’m on the exercises for that portion. So, here’s an interesting question involving the concept of total unimodularity, which is apparently one of those foundational concepts in an area called polyhedral combinatorics.
A matrix \(\mat{A}\) is called totally unimodular if every square submatrix of \(\mat{A}\) has determinant 0 or \(\pm 1.\) The question is to show that every nonsingular totally unimodular \(n \times n\) matrix maps the lattice \(\mathbb{Z}^n\) bijectively onto itself.
Update (solution)
It’s easy peasy. Clearly each entry of \(\mat{A}\) is in \(\{-1,0,1\}\), so \(\mat{A}\) maps \(\mathbb{Z}^n\) into itself. The fact that the mapping is bijective follows easily from Cramer’s rule, the fact that \(|\mathrm{det}(\mat{A})| = 1,\) and the fact that all the minors of \(\mat{A}\) are integral.
This is an excellent program from the BBC.
I’m not sure why YouTube hasn’t taken it down due to copyright reasons, but until they do…
This is the first in a series.
Related posts:
Faster, cheaper computing makes it possible to create more and better models for calculating cash movements, which can be turned into trading instruments. Areas like leasing, mortgages and project finance have exploded – as has the entire financial derivatives market — thanks to cheap computing...
Soon, it becomes nearly impossible to say what is going on where, and you get events like the 1998 blow-up at Long Term Capital Management, the creation and destruction of the subprime mortgage market in 2008 and perhaps even the “flash crash” in 2010. JPMorgan’s loss seems to be the latest in that series.I've argued the dangers of reducing computational friction before. But here computational complexity comes in a different way. A derivative is just a function of current and future security prices. But a derivative complex enough can have a behavior that even its creator cannot understand. The Clay Math Institute offers a million dollars to settle "P v NP" but it cost Chase two billion.
I ran across this problem in a reddit side-bar job-ad, and was intrigued by the task (description paraphrased to decrease googleability):
Write a function
uint64_t bitsquares(uint64_t a, uint64_t b);
such that it return the number of integers in [a,b] that have a square number of bits set to 1. Your function should run in less than O(b-a).
I think I see how to do it in something like logarithmic time. Here’s how:
First off, we notice that we can list all the squares between 0 and 64: these are 0, 1, 9, 16, 25, 36, 49, and 64. The function I will propose will run through a binary tree of depth 64, shortcutting through branches whenever it can. In fact; changing implementation language completely, I wonder if I cannot even write it comprehensively in Haskell.
The key insight I had was that whenever you try to find the number of numbers with a bitcount matching some element of some list within the bounds of 0b0000…0000 and 0b000…01111…11, then it reduces to a simple binomial coefficient — n choose k gives the number of numbers with k bits set among the n last. Furthermore, we can reduce the total size of the problem by removing a matching prefix from the two numbers we test from.
Hence, we trace how many bits off the top agree between the two numbers. We count the set bits among these, subtract them from each representative in the list of squares, giving us the counts we need to hit in the remainder.
Write a’ for a with the agreeing prefix removed, and similarly for b’. Then the total count is the count for the reduced things from a’ to 0b000…01…111 plus the count for the reduced things from 0 to b’. The reduction count for b’ needs to be 1 larger than the one for a’ since in one case, we are working with the prefix before the varying bit increases, and in the other, we work with the prefix after the varying bit increases — the latter count is not really from 0 to b’, but this is a useful proxy for the count from 0b0000…010…000 to b’ with the additional high bit set.
In code, I managed to boil this down to:
import Data.Word
import Data.Bits
import Data.List (elemIndices)
bitsquare :: Word64 -> Word64 -> Word64bitsquare a b = bitcountin a b squares -- # integers in [a,b] with square # of 1
s
squares = [1,4,9,16,25,36,49,64] :: [Word64]
allones = [fromIntegral (2^k - 1) | k - [1..64]]
choose n 0 = 1
choose 0 k = 0
choose n k = (choose (n-1) (k-1)) * n `div` k
popCount :: Word64 -> Word64
popCount w = sum [1 | x - [0..63], testBit w x]
-- # integers in [a,b] with 1-counts in counts
bitcountin :: Word64 -> Word64 -> [Word64] -> Word64
bitcountin a b counts
| a > b = 0
| a == b = if popCount b `elem` counts then 1 else 0 | (a == 0) && (b `elem` allones) = sum [choose n k | n - [popCount b], k - c
ounts]
| otherwise = (bitcountin a' low [c-lobits | c - counts, c>= lobits]) +
(bitcountin hi b' [c-hibits | c - counts, c>= hibits])
where
agreements = [(testBit a n) == (testBit b n) | n - [0..63]]
agreeI = elemIndices False agreements
prefixIndex = last agreeI
prefixCount = sum [1 | x - [prefixIndex..63], testBit a x]
a' = a .&. (2^prefixIndex - 1)
b' = b .&. (2^prefixIndex - 1)
low = 2^prefixIndex - 1
hi = 0
lobits = prefixCount
hibits = prefixCount+1
(Paraphrase) Find a 4-coloring of the 17x17 grid that has
no monochromatic rectangles. For $289.00. It was solved in 2012
by Bernd Steinbach and Christian Posthoff (I posted about it
here
and will post their paper when they make it it is public, which should be soon.)
Even though it was solved, it seemed to be a hard problem.
(Paraphrase) Consider the following problem:
Given (N,M,c,f) where f is a partial c-coloring of NxM,
can f be extended to a total c-coloring of NxM (without mono rectangles)?
Is this problem NP-complete?
8 May 2012
In this Newsletter:
1. Your math secret
2. TED-ED – Flip your lesson
3. Image conversion project – thank you!
4. Twitter update
5. Math puzzle
6. Friday math movie – The $8 billion iPod
7. Final thought – Apply yourself
 |
Do you have a secret about your math experiences? Several interesting ones have gone up already. Share yours too! You don’t have to reveal your real name. |
This one is mostly for teachers, but math students should also find something interesting here.
TED (the place where the world’s great thinkers get us to re-evaluate the way we look at the world) recently released TED-ED.
TED-ED is a collection of "Lessons worth sharing". There are lesson plans built around interesting TED talks, and you can either use those lessons, modify them to your own needs, or create a completely new lesson based on the talk.
“Flipping” your lesson involves getting students to learn some things before the actual in-class lesson. This allows students more time to process the concepts during class time, rather than hearing the concepts for the first time. Flipping gained a lot of momentum with the growth of resources like the Khan Academy.
This tour explains the TED-ED concept.
Here is the Math Category
There’s also a Math in Real Life series of TED talks.
There are now over 3000 people following IntMath on Twitter! The 3,000th follower was a design engineer.
There are many good people sharing educational messages and resources there. It’s a great place for getting to know people and for sharing interesting finds.
Why don’t you join us?
A big thank you to all those who helped out in the recent IntMath image conversion project. There were a few thousand images converted and now it’s all done.
I’m in the process now of removing the old images and replacing them with the new ASCIIMathML-produced, MathJax output equivalents.
You an see some examples of converted images in the math on these pages:
Matrix Multiplication and Inverse
Related Rates (calculus)
Several people wrote in to answer the last puzzle about numbers. The correct answers were 41 and 50. Great to see reasons given for the answers!
New Puzzle
Line ABCD is a diameter of a circle whose radius is r. Length AB = BC = CD. Semicircles are drawn on AB and BD to create the shaded figure as shown.
What is the perimeter of the shaded figure?
 |
Rob Reid gets us to think about how silly the music and movie industries have been regarding copyright. He explains Copyright Math. |
Lee Iacocca, colorful chairman of Chrysler Motors for many years, was named one of the top American CEOs of all time. The following quote could apply to what we do with our math knowledge:
Apply yourself. Get all the education you can, but then, by God, do something. Don’t just stand there, make it happen. [Lee Iacocca]
Until next time, enjoy whatever you learn.
Related posts:
For a long time, people got used to being lazy. If computers become twice as fast every 1.5 to 2 years, there is no point in investing much efforts in writing efficient code. If something does not run fast enough, simply wait for the next generation of Intel x86 and everything will be resolved. In particular, CPUs became fast enough that traditional programming languages and efficient data structures and algorithms were being abandoned in favor of high level scripting languages whose most sophisticated data structure is an associative array. Suddenly, every Joe-hoe could become a programmer developing sophisticated Web applications with no effort – no need for hard earned computer science degrees anymore.Let's ignore the issue as to whether Moore's law is really coming to an end (Moore's law has had 5-10 years left in it since Gordon Moore developed his law). Friedman misses the bigger point, an end of Moore's law will do great harm to Computer Science.
X={a^nb^nc^n | n ∈ N}is NOT a CFL is easy using the pumping theorem.
Y={w | number of a's, b's and c's in w is the same}How do you prove Y is not regular?
Recall that if α is a regular expression then $(α) is the
set of strings that α generates.
Recall that if G is a CFG then L(G) is the set of strings generated by G.
Prove the following by induction on the formation of a regular expression:
For all regular expressions α there exists a Context Free Grammar G
such that L(α)=L(G).
You cannot use PDA's (Push Down Automata). (If you do not know what this is,
do not worry.)
I had a question that I was going to ask on Math Overflow, but after some research I managed to find the answer.
Finite simple groups have a complete classification. I was wondering if there were any weakenings of the axioms of group that also allowed a complete classification of the simple objects. (Here, I mean no nontrivial quotients.) Surprisingly, there’s a classification for semigroups. In the theory of semigropus the term “Simple& is used for a weaker notion. Semigroups with no nontrivial quotients are known as “congruence-free”. The classification of finite congruence-free semigroups splits into two cases: for semigroups with a zero (an element 0 such that 0x = 0) there’s an explicit construction, while a congruence-free semigroup without a zero must be a simple group.
Another direction to generalize is weaken the form of associativity. The most-studied weakening is the Moufang property, which includes the octonions as a non-trivial example. Here, the complete classification is also known: a finite simple Moufang loop is either a group or a Paige loop, which is a non-associative construction closely related to the octonions, but defined over a finite field. It’s interesting that in this case, the one non-associative family resembles simple groups of Lie type, in that it’s parameterized by the finite fields. This classification relies non-trivially on the classification of simple groups, in that the explicit classification is used to rule out any other non-associative examples.
The paper Octonions, simple Moufang loops and triality by Gábor Nagy and Petr Vojtechovský, explains Moufang loops, and how the classification of non-associative Moufang Loops reduces to a question about finite simple groups.
Roughly half of the CISE faculty would be offered the opportunity to move to Electrical and Computer Engineering, Biomedical Engineering or Industrial and Systems Engineering. These faculty would continue to support the graduate and research mission in the Computer Engineering degree track. The choice of which faculty and which departments will be made based on fit with the research program and with the receiving departments. Staff positions in CISE which are currently supporting research and graduate programs would be eliminated. The activities currently covered by TAs would be reassigned to faculty and the TA budget for CISE would be eliminated. The faculty remaining in CISE would then focus their efforts on teaching and advising students in the existing Computer Science BS and MS degree programs, offered through both the College of Engineering and the College of Liberal Arts and Sciences. Their assignments would change to reflect this new educational mission with sole focus on delivering quality education for students in these degree programs. Any faculty member who wishes to stay in CISE may do so, but with a revised assignment focused on teaching and advising.In other words Florida is eliminating core Computer Science research, something that makes no sense for a state flagship research university in this day and age. There is a website and petition protesting the move which has caused the Dean to respond. Perhaps because of geographical closeness, this was a big topic of discussion when I was down at Georgia Tech last week. The current and founding Deans of the College of Computing at GT wrote strong letters to the Florida president. The CRA has also expressed their concern.
The first half of our Alan Turing Centenary lecture series is over, and we've got all three of our talks up on mathtube.org. You can skip the first one, it's pretty boring, but Mike Williams on early computers and John Ferris on Turing and WWII codebreaking are well worth your time!
Let \(\mat{P}_{\mathcal{U}}\) denote the projection unto a \(k\)-dimensional subspace of \(\C^{n}.\) We say \(\mathcal{U}\) is \(\mu\)-coherent if \((\mat{P}_{\mathcal{U}})_{ii} \leq \mu \frac{k}{n} \) for all \(i = 1, \ldots, n.\)
Let \(\mat{A} \in \C^{n \times n} \) be a SPSD matrix whose top \(k\)-dimensional invariant subspace is \(\mu\)-coherent. Given \(\delta > 0\) and \(\mat{S} \in \C^{n \times \ell}\), where \(k < \ell \ll n,\) is there a matrix \(\mat{E}_{\delta,\mat{S}} \in \C^{n \times n} \) such that
It’d be fine if instead of (2) holding, the coherence of the top \(k\)-dimensional invariant subspace of \(\hat{\mat{A}}\) is slightly larger than that of \(\mat{A}\).
William Gasarch SIGACT News Hi William, The winners of Russia's prestigious Debut Prize are presently in the U.S. The newest of the winning books is Irina Bogatryreva's Off The Beaten Track which contains her story and two others about hitchhiking in Russia. Irina is also available for interviews as she speaks English fluently! Please let me know if you would like to receive a copy of this new and interesting novel. The Debut Prize winners will be visiting select cities (Washington, Boston and New York) during their stay and will also return in June for BEA. I look forward to your thoughts. Best, Shirley
> {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, GeneralizedNewtypeDeriving #-}
> {-# LANGUAGE FunctionalDependencies, TypeSynonymInstances #-}
> import Control.Monad
> import Control.Monad.Writer hiding (lift)
Shannon entropy> data P a = P [(a, Float)] deriving ShowWe can easily compute the expected value of a distribution, and its entropy, like this:
> instance Functor P where
> fmap f (P xs) = P [(f a, p) | (a, p) <- xs]
> instance Monad P where
> return x = P [(x, 1)]
> P xss >>= f = P [(y, p*q) | (pxs, p) <- xss, let P ys = f pxs, (y, q) <- ys]
> expectation0 (P xs) = sum [x*p | (x, p) <- xs]An important property of entropy is known as the grouping property which can be illustrated through an example tree like this:
> entropy0 (P xs) = -sum [if p==0 then 0 else p*log p/log 2.0 | (_, p) <- xs]
> bernoulli p a b = P [(a, p), (b, 1-p)]Now the branch at the root of the tree:
> root = bernoulli 0.3 False TrueWe can compute the entropy for the distrbution on the leaves:
> test1 = entropy0 $ doOr the sum of the root entropy and the expected subtree entropy:
> x <- root
> if x
> then bernoulli 0.2 3 4
> else bernoulli 0.4 5 6
> test2 = entropy0 root + (expectation0 $ doYou can confirm for yourself that test1 == test2.
> x <- root
> if x
> then return $ entropy0 (bernoulli 0.2 3 4)
> else return $ entropy0 (bernoulli 0.4 5 6))
> dist = bernoulli 0.3 (bernoulli 0.4 5 6) (bernoulli 0.2 3 4)And now we expect the equality of test3 and test4:
> test3 = entropy0 $ doThere's a more elegant way of writing this. Define:
> x <- dist
> x
> test4 = entropy0 dist + (expectation0 $ do
> x <- dist
> return $ entropy0 x)
> left0 dist = entropy0 (join dist)Now we expect left0 dist and right0 dist to always be equal. We've almost generalised to something that makes sense in the context of monads other than probability.
> right0 dist = entropy0 dist+expectation0 (fmap entropy0 dist)
> class Algebra m a | m -> a whereWe'll assume that when m is a monad, any instance satisfies the two laws above. Here's the instance for probability:
> expectation :: m a -> a
> instance Algebra P Float whereIn keeping with the notion that entropy measure diversity let's also define:
> expectation (P xs) = sum [x*p | (x, p) <- xs]
> class Diverse m r | m -> r wherewith the instance:
> entropy :: m x -> r
> instance Diverse P Float whereIt's not clear what laws we need but for now we'll assume a generalised entropy satisfies left dist == right dist :
> entropy (P xs) = -sum [if p==0 then 0 else p*log p/log 2.0 | (_, p) <- xs]
> left dist = entropy (join dist)We'll call that the generalised grouping law.
> right dist = entropy dist+expectation (fmap entropy dist)
> data Tree a = Leaf a | Fork (Tree a) (Tree a) deriving ShowLists
> instance Functor Tree where
> fmap f (Leaf a) = Leaf (f a)
> fmap f (Fork l r) = Fork (fmap f l) (fmap f r)
> instance Monad Tree where
> return x = Leaf x
> Leaf a >>= f = f a
> Fork l r >>= f = Fork (l >>= f) (r >>= f)
> instance Algebra Tree Float where
> expectation (Leaf a) = a
> expectation (Fork l r) = 0.5*expectation l+0.5*expectation r
> instance Diverse Tree Float where
> entropy (Leaf a) = 0
> entropy (Fork l r) = 1+0.5*entropy l+0.5*entropy r
> newtype L a = L [a] deriving (Show, Monad, Functor)Tsallis entropy
> instance Algebra L Int where
> expectation (L xs) = sum xs
> instance Diverse L Int where
> entropy (L xs) = length xs-1
> q = 2.5And again we find our generalised grouping rule for entropy holds.
> data T a = T [(a, Float)] deriving Show
> instance Functor T where
> fmap f (T xs) = T [(f a, p) | (a, p) <- xs]
> instance Monad T where
> return x = T [(x, 1)]
> T xss >>= f = T [(y, p*q) | (pxs, p) <- xss, let T ys = f pxs, (y, q) <- ys]
> instance Algebra T Float where
> expectation (T xs) = sum [x*p**q | (x, p) <- xs]
> instance Diverse T Float where
> entropy (T xs) = (1-sum [p**q | (_, p) <- xs])/(q-1)
> data D a = D { re::a, im::a } deriving (Show, Ord, Eq)
> instance Num a => Num (D a) where
> fromInteger n = D (fromInteger n) 0
> D a a'+D b b' = D (a+b) (a'+b')
> D a a'*D b b' = D (a*b) (a*b'+a'*b)
> D a a'-D b b' = D (a-b) (a'-b')
> instance Fractional a => Fractional (D a) where
> fromRational n = D (fromRational n) 0
> D a a'/D b b' = let q = 1/b in D (a*q) ((-a*b'+a'*b)*q*q)
> lift x = D x 0
> d f x = im (f (D x 1))
> raised f = re . f . lift
> raised2 = raised . raised
> raised3 = raised2 . raised
The Cn are the n-times (automatically) differentiable functions. Unfortunately the Endo defined in Data.Monoid acts the wrong way round from what I want so I need a Dual:> type C1 = Dual (Endo (D Double))A silly Show instance that simply evaluates a function at a number I chose randomly: 1.234.
> type C3 = Dual (Endo (D (D (D Double))))
> type C4 = Dual (Endo (D (D (D (D Double)))))
> instance Eq (Endo (D Double))
> instance Ord (Endo (D Double))
> instance Show (Endo (D Double)) whereWe can give Q a a geometrical interpretation. The underlying type is a pair (a, C4). If we think of elements of C4 as charts charts on a piece of Riemann surface then for any
> show (Endo f) = show (f 1.234)
> instance Num C1 where
> fromInteger n = Dual (Endo (\x -> fromInteger n))
> Dual (Endo f)+Dual (Endo g) = Dual (Endo (\x -> f x + g x))
> Dual (Endo f)-Dual (Endo g) = Dual (Endo (\x -> f x - g x))
> Dual (Endo f)*Dual (Endo g) = Dual (Endo (\x -> f x * g x))
> instance Fractional C1 where
> fromRational n = Dual (Endo (\x -> fromRational n))
> Dual (Endo f)/Dual (Endo g) = Dual (Endo (\x -> f x / g x))
> newtype Q a = Q (Writer C4 a) deriving (Monad, Functor)
> instance Algebra Q C1 whereNow we can define the Schwarzian derivative:
> expectation (Q ma) = let (Dual (Endo a), Dual (Endo f)) = runWriter ma
> in Dual (Endo (\x -> a (raised3 f x)*(raised2 (d f) x)^2))
> schwarzian f x = let f0 = raised3 f xAnd somwehat bizarrely, we now have a generalised entropy:
> f1 = raised2 (d f) x
> f2 = raised (d $ d f) x
> f3 = (d $ d $ d f) x
> in f3/f1-1.5*(f2/f1)^2
> instance Diverse Q C1 whereThis is the construction that gives rise to the Virasoro algebra which plays such an important role in String Theory.
> entropy (Q ma) = let (_, Dual (Endo f)) = runWriter ma
> in Dual (Endo (\x -> schwarzian f x))
> test :: (Algebra m t, Diverse m t, Num t, Functor m, Monad m) => m (m x) -> IO ()
> test x = do
> print (left x, right x)
> main = do
> test $ L [L [1, 2, 3], L [2, 3, 4], L [1], L [5], L [2, 7::Int]]
> test $ P [(P [(0, 0.5), (1, 0.5)], 0.5), (P [(2, 0.5), (3::Int, 0.5)], 0.5::Float)]
> test $ T [(T [(0, 0.5), (1, 0.5)], 0.5), (T [(2, 0.5), (3::Int, 0.5)], 0.5::Float)]
> test $ Leaf (Leaf 1 `Fork` Leaf 2) `Fork` Leaf (Leaf 3 `Fork` (Leaf 4 `Fork` Leaf 5))
> test $ (Q (writer
> (Q (writer (Dual (Endo (\x -> x)),
> Dual (Endo (\x -> x^2+1)))),
> Dual (Endo (\x -> (2+x)/(3+x*x))))) :: Q (Q C3))
2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,yAnswers and Commentary. See also this blog entry on the problem.
We note that one of the papers presented in the workshop is not included in the proceedings. This paper, "Functor is to Lens as Applicative is to Biplate: Introducing Multiplate" by Russell O'Connor, is accessible as arXiv:1103.2841v2 [cs.PL].Russell gives his account but he focuses on ArXiv instead of the public domain aspect. In the STOC CFP we encourage putting your submissions on ArXiv and similar sites. The issue that worried ACM was the loss of rights. ACM could have published the paper, it was in the public domain, but it wouldn't have control of that publication and didn't want to set precedent. Scott Delman of the ACM responded here.
It is well known that, both in constructive mathematics and in programming languages, types are secretly topological spaces and functions are secretly continuous. I have previously exploited this in the posts Seemingly impossible functional programs and A Haskell monad for infinite search in finite time, using the language Haskell. In languages based on Martin-Löf type theory such as Agda, there is a set of all types. This can be used to define functions $\mathbb{N} \to \mathrm{Set}$ that map numbers to types, functions $\mathrm{Set} \to \mathrm{Set}$ that map types to types, and so on.
Because $\mathrm{Set}$ itself is a type, a large type of small types, it must have a secret topology. What is it? There are a number of ways of approaching topology. The most popular one is via open sets. For some spaces, one can instead use convergent sequences, and this approach is more convenient in our situation. It turns out that the topology of the universe $\mathrm{Set}$ is indiscrete: every sequence of types converges to any type! I apply this to deduce that $\mathrm{Set}$ satisfies the conclusion of Rice’s Theorem: it has no non-trivial, extensional, decidable property.
To see how this works, check:
The Agda pages can be navigated be clicking at any (defined) symbol or word, in particular by clicking at the imported module names.
Sanjeev Arora is one of the architects of the Probabilistically Checkable Proofs (PCP) theorem, which revolutionized our understanding of complexity and the approximability of NP-hard problems. He helped create new approximation algorithms for fundamental optimization problems such as the Sparsest Cuts problem and the Euclidean Travelling Salesman problem, and contributed to the development of semi-definite programming as a practical algorithmic tool. He has played a pivotal role in some of the deepest and most influential results in theoretical computer science, and continues to inspire colleagues and new generations of researchers.Congratulations to Sanjeev!
Math was a mistake, I made it too hardOr at least I thought he said it. I have repeated this quote both in the blog and as a comment on Scott's blog. As I noted on my blog, if you Google
"Math was a mistake, I made it too hard"all of the hits that you get lead back to me. This is still true. (Though it won't be after this post goes up.)
"Mathematics, that was a mistake. I should have made the whole thing a little easier"I think my version is better.
The capitalists will sell us the rope with which we will hang them.He did say:
The capitalists will furnish credits which will serve us for the support of the Communist Party in their countries and, by supplying us materials and technical equipment which we lack, will restore our military industry necessary for our future attacks against our supplier. To put it in other words, they will work on the preparations of their own suicide. (The Yale Book of Quotations (2006))Both for George Burns and Stalin I am troubled- are we better off using the pithy version of the quotes, which DOES capture what they meant, or the original?
There is no 2-digits number that is the sum of the squares of its digits.One crude measure of elegance is to minimize the number of numbers that you need to check directly are not the sum of the squares of their digits. With this in mind. With this in mind, here are several proof sketches.
There is no x &geq 2 that is the sum of the squares of its digits.The cases of 2 &leq x &leq 9 and x &geq 100 can be done with zero checks, so using the best proof of the last theorem, we can do this theorem with 2 checks.
The only 3-digits number that is the sum of the cubes of its digits is 153. (NOTE ADDED LATER: This is INCORRECT. A commenter pointed out that 370, 371, 407 also work. I will fix the proof and statement later and see if these are the only ones. Score a point for the `do it by a computer enumeration' argument!)I have a proof of this which is... not quite elegant but not brute force. I get it down to only 21 CHECKS. If you have a better proof in terms of NUMBER OF CHECKS that is not contrived to reduce NUMBER OF CHECKS I would be very interested to see it. Of course, I cannot define contrived rigorously or elegantly.
I had a dozen eggs in the fridge that I need to use up by Wednesday; now I’m down to four. I made Jaffa cakes last week (not bad, but not memorable, and definitely not worth the effort: my main complaint is that the cake portion is bland and has a too-tough texture) and I left some chocolate blueberry cookie dough sitting in the fridge overnight which I’ll bake up tonight. That accounted for four of the eggs. This post is about the two meals that account for another four, and maybe the remaining four also 
Steak, eggs, and vegetables in sauce
I’m in love with this dish because it’s super simple to prepare, filling, and not too unhealthy: steak, eggs, and steamed veggies in a Dijon sauce. Surprisingly, considering how much I love meat, the star of the show here is the veggies in sauce: steamed baby carrots and French green beans (haricot verts) with an emulsion of Dijon mustard, red wine vinegar, EVOO, and some salt. Basically, it’s a quick and dirty substitute for Sauce Dijon.
If I’d known sauce + steamed vegetables was such a winning combination (don’t ask me why it took so late in life for me to get a clue) I would be a much healthier person My mission for next week is to learn how to make Hollandaise sauce and its derivatives, and find other vegetables to smother in sauce. No doubt Alton Brown has something interesting to say on the matter.
.jpg)
This meeting will take place in the period July 2-6, at the ICMS in Edinburgh, Scotland. The theme will be applications of topological methods
in various domains. Invited speakers are
J.D. Boissonnat (INRIA Sophia Antipolis) (Confirmed)
R. Van de Weijgaert (Groningen) (Confirmed)
N. Linial (Hebrew University, Jerusalem) (Confirmed)
S. Weinberger (University of Chicago) (Confirmed)
S. Smale (City University of Hong Kong) (Confirmed)
H. Edelsbrunner (IST, Austria) (Confirmed)
E. Goubault (Commissariat à l’énergie atomique, Paris) (Confirmed)
S. Krishnan (University of Pennsylvania) (Confirmed)
M. Kahle (The Ohio State University) (Confirmed)
L. Guibas (Stanford University) (Confirmed)
R. Macpherson (IAS Princeton) (Tentative)
A. Szymczak (Colorado School of Mines) (Confirmed)
P. Skraba/ M. Vejdemo-Johansson (Ljubljana/St. Andrews) (Confirmed)
Y. Mileyko (Duke University) (Confirmed)
D. Cohen (Louisiana State)
V. de Silva (Confirmed)
There will be opportunities for contributed talks. Titles and abstracts should be send to Gunnar Carlsson at gunnar@math.stanford.edu.
The conference website is located at http://www.icms.org.uk/workshops/atmcs5. Those interested should register there as soon as possible so that we can obtain an idea of the number of participants.
For the organizing committee,
Gunnar Carlsson
I’ve been trying to learn about stacks, something that is much easier in the Internet age. The Stacks Project is a collaborative textbook that introduces the subject from the ground up, including all of the machinery necessary. The book is already up to 3000(!) pages.
[a for x in y]Here the single letter variables are 'metavariables' representing fragments of Python code. To a good approximation this is equal to:
map(lambda x: a, y)(BTW Everything I say here is "to a good approximation". Python is an incredibly complex language and I'm not good enough at it to make any categorical statements about when one fragment of code is the same as another.)
[(y, z) for y in [1, 2] for z in ['a', 'b']]This isn't quite the same as
[[(y, z) for z in ['a', 'b']] for y in [1, 2]]but it's close. The latter produces nested lists whereas the first gives one flat list. We can think of nested comprehensions as applying a flattening operation. Let's use list comprehension to implement flattening:
def concat(xs):We now write our nested comprehension as:
return [y for x in xs for y in x]
concat([[(y, z) for z in ['a', 'b']] for y in [1, 2]])We know how to write non-nested comprehensions using map so we get:
concat(map(lambda y: [(y, z) for z in ['a', 'b']], [1, 2]))And rewriting the inner comprehension we get:
concat(map(lambda y: map(lambda z: (y, z), ['a', 'b']), [1, 2]))Every time we add another level of nesting we're going to need another concat. But the innermost map doesn't have a concat. Purely for reasons of symmetry we can ensure every map has a concat by enclosing the innermost element as a singleton list:
concat(map(lambda y: concat(map(lambda z: [(y, z)], ['a', 'b'])), [1, 2]))Every map has a concat so we can simplify slightly. Let's define:
def concatMap(f, xs):Our expression becomes:
return [f(y) for x in xs for y in x]
def singleton(x):
return [x]
concatMap(lambda y: concatMap(lambda z: singleton((y, z)), ['a', 'b']), [1, 2])Importantly we've completely rewritten the comprehension in terms of concatMap and singleton. By changing the meaning of these functions we can change the meaning of comprehension notation, or at least we could if the Python interpreter defined comprehension this way. It doesn't, but we can still reason about it. Although any comprehension that doesn't use ifs can be rewritten to use these functions, I won't give a formal description of the procedure. Instead I'll provide code to perform the rewrite later. While I'm at it, I'll also handle the ifs.
y == [x for x in y]In other words
y == concatMap(lambda x: singleton(x), y)At this point I could give a whole bunch more laws but it's time to own up.
import mathI have defined our functions so that comprehension syntax gives us the continuation monad. This makes continuation passing style relatively painless in Python. (At least easier than chaining many lambdas.) I have then defined callCC to be similar to its definition in Haskell. There are many uses for callCC including the implementation of goto. Above I use it in a trivial way to throw exceptions.
def __concatMap__(k, m):
return lambda c:m(lambda a:k(a)(c))
def __singleton__(x):
return lambda f:f(x)
def callCC(f):
return lambda c:f(lambda a:lambda _:c(a))(c)
def __fail__():
raise "Failure is not an option for continuations"
def ret(x):
return __singleton__(x)
def id(x):
return x
def solve(a, b, c):
return callCC(lambda throw: [((-b-d)/(2*a), (-b+d)/(2*a))
for a0 in (throw("Not quadratic") if a==0 else ret(a))
for d2 in ret(b*b-4*a*c)
for d in (ret(math.sqrt(d2)) if d2>=0 else throw("No roots"))
])
print solve(1, 0, -9)(id)
print solve(1, 1, 9)(id)
print solve(0, 1, 9)(id)
I’m reading Santosh Vempala’s survey “Geometric Random Walks: A Survey,” and already I’m puzzled at one of the very first definitions he gives.
Define a Markov chain as a state space sigma algebra pair \((K, \mathcal{A})\) with transition probability measures given by \(P_u\) for each \(u \in K.\)
A distribution \(Q\) on \((K, \mathcal{A})\) is called stationary if one step from it gives the same distribution, i.e., for any \(A \in \mathcal{A},\)
\[
\int_A P_u(A) \, dQ(u) = Q(A).
\]
This definition makes sense in words, but mathematically it doesn’t seem sound: unless \(P_u(A) = 1\) a.e. (with respect to \(u \in A\)), this equality can’t hold. I must be missing something…
Update:
The definition should involve integration over the whole space:
A distribution \(Q\) on \((K, \mathcal{A})\) is called stationary if one step from it gives the same distribution, i.e., for any \(A \in \mathcal{A},\)
\[
\int_K P_u(A) \, dQ(u) = Q(A).
\]
That this is so can be seen from the discrete case. Just goes to show you that you have to be careful even when reading peer-reviewed articles.
It's Alan Turing's centenary, and we've been celebrating it at the University of Calgary with a series of lectures. This term, we've had a talk on the decision problem, one (by Mike Williams) on Turing and early electronic comupters, and one coming up on March 27, by John Ferris, on Alan Turing and codebreaking in WWII. Yesterday, we screened the biopic Breaking the Code, with Derek Jacobi as Alan Turing (which you can watch on YouTube in its entirety!). The Pacific Institute for the Mathematical Sciences is paying to have the lectures videotaped and the'll be appearing on mathtube.org as they become available. The lecture by my distinguised colleague in the Computer Science department, Mike Williams, was just posted a couple of days ago. Mike is a former President of the IEEE Computer Society, editor in chief of the Annals of the History of Computing, and head curator for the Computer History Museum. So he knows his history of computing machinery, and gave us a wonderful talk about Turing's role in the development of early digital computers. (There's also a lecture by me on the 1936 paper, but that's much less interesting.) Thanks to generous funding from the Faculty of Science, we also have nice posters, like the one below, advertising our last talk for the Winter term, by my distinguished colleague in the History Department, John R. Ferris.
Matija and I are pleased to announce a new major release of the eff programming language.
In the last year or so eff has matured considerably:
Math is a domain that improves with a new idea or with a new problem every single second. This is why the aim of our site, Planet Math, is to gather the most recent info on math subjects. And how do we do that? By selecting the best contents from weblogs that are focused on various mathematic topics! Since we actualize out content every day, everything you find and read on Planet Math is recently updated and very new. Furthermore, the authors of these blogs are specialists, people who are highly interested and experienced in mathematics.
Updated on May 20, 2012 09:07 AM UTC. Entries are normalised to UTC time.
Powered by Planet!
Is this planet missing something?
Do you want to add/remove your blog's feed?
We would be happy to get your feedback.
You can contact us with the email address below:
contact [at] planet-math.org
A Mathematician's Scratchpad A Neighborhood of Infinity Ars Mathematica ChapterZero Computational Complexity Epsilon-Delta Gaussian Nodes Homeschool Math Blog Kate's Math LogBlog Logicomp Math News from Mathforge.net Mathematics - Topix.net Mathematics and Computation Michi's blog P.P. Cook's Tangent Space Polymathematics That Logic Blog The New Math True Artificial Intelligence ecstatic over numbers it's not about the sex- it's about the math! logicandlanguage.net squareCircleZ