The Kentucky State Police of Post 2 in Madisonville have released their statistical report for the month of June.
The Kentucky State Police of Post 2 in Madisonville have released their statistical report for the month of June.
MOST young people jailed for breaching bail conditions have not committed another crime but have broken curfews or failed to stay with parents, a controversial report by the NSW Bureau of Crime Statistics and Research shows.
Many readers write to me asking for examples of “real life math”. Here’s a resource that you may find useful: Math Illuminated.
Are you interested in the connection between math and real life or maybe you’re a teacher and looking for some real life math to share with your students? This resource may help.
As their blurb says:
Mathematics Illuminated is a thirteen-part series for adult learners and high school teachers. The series explores major themes in the field of mathematics, from humankind’s earliest study of prime numbers, to the cutting-edge mathematics used to reveal the shape of the universe.
The materials for each topic include videos, Flash interactives, a “textbook” with good explanations of the concepts, a facilitator guide and a bibliography for further reading. There’s also an interactive Math Family Tree which shows how various discoveries in math are related, and when they appeared (via a timeline).
I mentioned Mathematics Illuminated before in Friday Math Movie – Math Illuminated but I was concentrating on the videos at that time.
So next time you are wondering how to convert a math lesson into a real life scenario, Math Illuminated may give you some starter ideas.
Who’s Counting – John Allen Paulos examines the news through numbers gives a fascinating insight into the math behind current news events.
Paulos is a professor of mathematics at Temple University in Philadelphia and is well-known for his book Innumeracy: Mathematical Illiteracy and its Consequences (1988) in which he said:
I’m distressed by a society which depends so completely on mathematics and science and yet seems to indifferent to the innumeracy and scientific illiteracy of so many of its citizens.
His monthly Who’s Counting series is an attempt to address such innumeracy and scientific illiteracy.
The most recent articles (for Jan to Jun 2009) include:
He addresses a range of issues in these articles. One that caught my eye: How to Calculate Chances of Doomsday.
Paulos is worth checking out.
Here we see a regular dodecahedron. (These don't look great as static images, I know, but the program allows you to rotate the figures which makes them a lot easier to discern.) Suppose we were to twist two of the opposite pentagonal faces; then we'd get something that looks a little like this:
In case you couldn't tell from the shape, the background has turned light yellow to indicate that this permutation is not in fact an automorphism of the dodecahedron. This is a platform independent Java application, and I'll post a download as soon as my web hosting comes back up. If anyone would like to look over my Java code and tidy it up, and/or make it into a workable applet, that'd be great; I really don't know Java and this took me way longer to write than it should have.
Let X1, X2, ... XN be i.i.d. random variables, and let YN = [ X1 + X2 + ... + XN ] / N. Put f(N) = Median(YN). If μ = Mean(Xi), i.e. if that mean exists, then as N → ∞ we have f(N) → μ.Note that this limit can converge in circumstances where there is no mean -- for instance, it clearly always gives the axis of symmetry for a symmetric distribution, and there exist symmetric distributions which have no mean, e.g. the Cauchy distributions. So in broad terms this is a generalization of the concept of the mean.
Proof (thanks to Robert Israel): The Weak Law of Large Numbers states that, for ɛ>0, Pr{|YN - μ| ɛ} → 1 as N → ∞. For N sufficiently large, then, Pr{|YN - μ| ɛ} > 1/2, or in other words, more than half of the distribution for YN lies within the interval (μ - ɛ, μ + ɛ). In particular, at least half lies within (-∞, μ + ɛ), so there is no way that the median f(N) can exceed μ + ɛ; symmetrically, f(N) > μ - ɛ. Combining both sides, we see that |f(N) - μ| ɛ, which is to say that f(N) → μ as N → ∞.
Authors of those comments (and others who know stuff)--- please email me more exact references. I found some things on Google but it would be good to know what to read and what is a good source to reference. Preferable online.QUESTION: In a paper if you are using a result that is known how much detail should you put in?
Dear all,Please respond to Catarina at the email address above!
Recently (and admittedly very late!), I started thinking more seriously about the lack of gender balance in the areas in which I do most of my research, namely history and philosophy of logic and philosophical logic. What got me thinking was probably the (positive) noise being made at Feminist Philosophers. One of the issues raised by the Feminist Philosophers is the low proportion of women in most philosophy conferences (in particular as invited/keynote speakers); I realized that in the workshop I am organizing, there are only three women as speakers, including myself! So I think this is a matter that deserves further attention.
Richard Zach had a blog entry a while ago on the staggeringly low number of women publishing in the journals of the area (his data concerned the Journal of Philosophical Logic). From this sort of data it is all too easy to conclude that there simply aren't enough women around working in (philosophy of) logic and philosophical logic so as to redress the imbalance seen in conference lineups. But here again the usual analysis applies: the lack of female speakers at such conferences reinforces the idea that the area is just not 'for women', which in turn does not encourage young female students to pursue interests they might have in the area. Absence of female keynote speakers may also be a discouraging factor for other female researchers to submit papers to such conferences. Sally Haslanger has a wonderful piece on how vicious these mechanisms can be, which can be found here: Changing the Ideology and Culture of Philosophy: Not by Reason (Alone)
So the purpose of this message now is to question the widespread impression that there are not (or very few) prominent female logicians and philosophers of logic, people with the standing to be keynote speakers at major conferences. I was thinking it might be useful to compile a list of such people, sort of a handy device that could help those organizing conferences in the area to ensure a better gender balance among the speakers. Please send me names off list, and I will post the results to the whole list once we have a significant number of names. Just to give you an idea of what I have in mind, here are some women that would obviously be on such a list: Juliet Floyd, Penelope Maddy, Gila Sher, Delia Graff Fara. I’m sure there are many more such talented women working in the philosophy of logic and philosophical logic, so I look forward to many reactions!
Thanks!
Catarina
cdutilhnovaes at yahoo dot com
"I work hard at the beginning to set up a culture of responsibility for themselves. They are responsible for making sure they understand, for asking questions, for asking for more practice or another example.Now, I'm not claiming that middle and high school teachers could easily transfer these ideas to their classes... but perhaps they can, at least somewhat. Please discuss homework at Sam Shah's post.
When we come into class, we check the answers together. I will solve a problem or two on the board that I have learned over the years is confusing. Other than that, I expect them to ask for clarification if a problem is wrong.
They "grade" their own. If it's wrong, they are expected to take a minute right then to figure out why it was wrong. Usually it's a silly mistake. If not, they bookmark it to ask questions during our next work time.
I don't give any grades. I don't assess it. The final test/quiz is their grade. The homework is just them figuring out how to do the skills. They know they won't be graded on it. They know they won't be penalized for getting it wrong. They know that the whole point of the homework is to figure this math stuff out. If they get it wrong, they know they haven't mastered it and need to get help.
On the opposite side, if a student doesn't do their homework, I don't get too upset. We have a talk about how they hurt themselves, because now they don't have an accurate measure of if they can do it on their own. I can't help them because they didn't get the opportunity to make their mistakes before the test. However, I have a few who don't need to do homework. They still earn A's on the final test. They learned it by being in class and paying attention.
With those who obviously do need the homework practice, but aren't doing it, I problem solve that on a case-by-case basis.
It changes the whole culture of learning and mastery in the classroom. But it is VERY important to set up that culture at the beginning."
John Cook from The Endeavour blog shows us an optical illusion that is so fooling that I couldn't believe my eyes at first. Quite amazing. He also makes an analogy from the optical illusion to a "mathematical" illusion within his own work.
by Louisa Gilder and “Gina Says,” Adventures in the Blogsphere String War "selected and edited" by Gil Kalai. While vastly different in style they both feature scientists happy to talk about and defend their own points of view in controversy theories but rarely willing to reconsider those views.
I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the University of Arkansas. The co-chairs of the organizing committee were Rusell Deaton and Jin-Woo Kim, who I thought did a great job. The research presented, and the backgrounds of the attendees, were diverse from experimental nanochemistry to theoretical computer science. I'll highlight a few elements of the program that had TCS and complexity flavor.
Jim Aspnes and Kenichi Morita gave TCS plenary talks. Aspnes introduced the audience to the computational theory of “population protocols” (see here for a survey) a theory of computation over a large network of agents who each possess very limited computational power. This theory can model ad hoc wireless networks, and (potentially) smart molecules interacting in solution. Morita surveyed results on reversible cellular automata and presented animations that showed the inner workings of several such devices. A reversible computation device is one in which each noninitial configuration has exactly one preceding configuration. Many models of natural computing are reversible models.
NP-completeness of the Direct Energy Barrier Problem Without Pseudoknots, due to Manuch et al., was presented by Anne Condon. The Energy Barrier Problem is decision problem about molecular folding. Given a structure in some initial configuration, does there exist a pathway through subsequent configurations to a final configuration, such that the step from each configuration to the next requires at most energy k, for some fixed k. The paper reduces a simplified version of the Energy Barrier Problem to 3-Partition, a known NP-complete problem.
Several papers discussed the theory and practice of building DNA-based circuits. I would like to focus on Signal Propagation and Propagation Delays in Molecular Circuits by Seelig and Soloveichik, as it puts forth the thesis that circuit depth is not the correct measure of time complexity for chemical circuits (in contrast to electronic circuits, or classical circuit complexity). They present a theoretical model to capture something that has been observed in the lab: when there are just a few molecules of a certain species in solution, the reactions that depend on them will be slow, because the species will interact with low probability, since contact with it is so rare. As a result, stepping through a circuit is not a linear process. Approach to completion of a circuit becomes increasingly slow the deeper the circuit is, because the later layers require the output of all the earlier layers. One possible fix for this is to catalyze the reactions in question, so the reactions occur quickly even if there is only a small amount of species present. The drawback to this is leakage: if a chemical species is not fully consumed at an earlier stage, its presence can build exponentially at later stages, leading to the circuit providing incorrect answers. All in all, an intriguing model that raises a lot of questions.
DNA 16 will take place in Hong Kong, and DNA 17 will be organized by Erik Winfree at CalTech. I'm looking forward to them both!
First: We (Bill Gasarch, Clyde Kruskal, Justin Kruskal) have in a paper of ours a summation that we proved. Is it new? Here is the summation: (It uses a sum that I previously inquired about here and got useful information, including that it was originally proved by Euler.)
Let p(x) ∈ Z[x] be a polynomial of degree n with constant term 0.Our proof is here.
p(s) - ∑k=1n(s+k-1 choose k)∑i=0k-1(k-1 choose i)(-1)i (p(s+i+1) - p(s+i)) = 0
(Side Request: How do you do a choose-sign in html?)
Second: I am, as always, tracking down lower bounds on the VDW numbers. I need the article An application of the Lovasz Local Lemma, a new lower bound for the Van der Warden numbers by Zoltan Szabo, Random Structures and Algorithms, 1990. Electronic preferred, but will take what you got. SO, if someone has it please email me article or pointer or whatnot. (Pointer might not work if your library has access to this journal, since ours does not have it in electronic or hardcopy.)
The Bertrand Russell Research Centre in 2010 will host a conference to celebrate the 100th anniversary of the publication of the first volume of Russell and Whitehead’s Principia Mathematica.
The publication in 1910 of the first of the three volumes of Russell and Whitehead’s Principia Mathematica was a landmark in the development of logic, the foundations of mathematics, and the application of logic in philosophy. The rapid development of these fields in the two decades after 1910 owes perhaps more to Principia Mathematica than to any other work. Subsequently, however, its lessons learnt in different ways by different people, it becomes more difficult to determine exactly what the world owes to this gigantic piece of work. Daunting both for its size and its technical difficulty, the book is now known more by reputation than by detailed study. Russell himself maintained, no doubt with some exaggeration, that he knew of only six people besides the authors who had read the entire three volumes. He remained dissatisfied with the foundations of the work and attempted a major revision (this time without Whitehead’s help) in a second edition published in 1925–27, which further complicated its historical legacy.
A century after its first appearance, a great deal has changed. Many of Russell’s working papers on the problems it addressed have been published, and this has led to significant re-interpretations of the work itself. Enough time has now passed to make it possible to evaluate what contributions it made, or failed to make, to philosophy, logic, and the foundations of mathematics.
Presenters Include: Patricia Blanchette, Charles Chihara, Warren Goldfarb, Ivor Grattan-Guinness, Leila Haaparanta, Allen Hazen, David Kaplan, Gregory Landini, Peter Simons, Alasdair Urquhart, and Richard Zach.
Submissions to the conference are sought in all areas relating to Principia Mathematica or to the development of logic and to the philosophy and foundations of mathematics in the years between the two editions.
Contributors are asked to submit two copies of an essay suitable for 30–45 minute presentation with an abstract no later than 1 January 2010 to:
Professor Nicholas Griffin, Director
The Bertrand Russell Research Centre
1280 Main Street West
Hamilton, Ontario
CANADA L8S 4M2
EMAIL: ngriffin@mcmaster.ca
FAX: 905-577-6930
Graduate students are also encouraged to submit. Announcements of acceptances for the program will be made by the end of February 2010.
Conference Co-Organizers:
Nicholas Griffin
The Bertrand Russell Research Centre
McMaster University
ngriffin@mcmaster.ca
Bernard Linsky
Department of Philosophy
University of Alberta
bernard.linsky@ualberta. ca
We've put it on our blogroll.
What will it be about? To quote Jon himself:
The blog will cover random topics, but especially crypto. It was started because there are currently no (active) crypto blogs and I hope this will become, to paraphrase Lance, a meeting place for the crypto community where we would have some discussions, sometimes quite heated, over the issues of concern to our communitySome advice for Jon and any new blogger:
Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.
This is a continuation of the topic in this blog entry.
In the June 17, 2009 issue of The New Republic, in an article called Plan of Attack, the term Prisoner's Dilemma was used and not explained. Does the public know what the term means? Are they supposed to learn what it means from context? I am asking these questions non-rhetorically. Here is the context and exact quote.
Context: Bob Woodward is going to do a book about the Obama White house. If you work in the White house, do you cooperate with him or not?
He (Bob Woodward) flashes a glimpse of what he knows, shaded in a largely negative light, with the hint of more to come, setting up a series of prisoner's dilemmas in which each prospective source faces a choice: Do you cooperate and elaborate in return for (you hope) learning more and earning a better portrayal-- for your boss and yourself? Or do you call his bluff by walking away in the hope that your reticence will make the final product less authoritative and therefore less damaging? If no one talks, there is no book. But if someone talks--- then everyone-- always talks.
Recall that a summation ∑i=0∞ ai Conditionally Cvgs if it cvg but ∑i=0∞ |ai| does not cvg.
Recall the following theorem.
Cond Cvg Thm: Let ∑i=0∞ ai be a cond. cvg sum. Let A ∈ R. Then there exists a way to rearrange the summation such that it cvg to A.What happens if instead of reals you have points in Rd? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)
Steinitz's Lemma Let d be a natural number, B be the unit ball in Rd, and V be a finite subset of B such that ∑v∈ V v = 0. Then there is an ordering v1, v2, ..., vn of the elements of V such thatThis can be used to show the following:v1 ∈ dB
v1+v2 ∈ dB
v1+v2+v3 ∈ dB
etc.
v1+...+vn ∈ dB
End of Statement of Steinitz's Lemma
d-dim version of Cond Cvg Theorem If a1, a2, a3,... ∈ Rd and ∑i=0∞ ai conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of Rd.
This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.
I have noticed that even though in the 80's and 90's a large number of FOCS, STOC, and SODA papers eventually appeared in journals (David Johnson even kindly edited a book that gave pointers to the journal versions of FOCS and STOC papers), the percentage appears to have declined significantly (I have not done a systematic analysis, but when I look for papers I often find that no journal version appeared.)
Most conference papers (even the top conferences) are not reviewed extremely carefully for correctness. The PC has a limited amount of time, and a large volume of papers to review.
What is the reason for this decline?
Are we so desperate to publish papers that we do not want to do a thorough job writing up the proofs after "staking our claim"?
Its very frustrating when when you are reading a paper and details are omitted or missing. Worse still, sometimes claims are made with no proof, or even proofs that are incorrect. Are we not concerned about correctness of results any more? The reviewing process may not be perfect, but at least its one way to have the work scrutinized carefully.
Now that proceedings are on CD's do we still need a strict 10 page limit on the conference version? Is this limit there to simply encourage people to submit to journals? If so, I am not sure its working.
What can we as a community do to ensure that results get properly reviewed and published in full in journals after they are published at a conference?
arrived yesterday. I loved my first Kindle which I used for reading books and the New York Times. But the Kindle couldn't handle mathematical papers. The DX has native PDF support. So how well does it do for our community's papers?
 |
| Progress! My Mandelbrot sleeve is progressing. It's been a year and a few months. I go in for some work for an hour or more every 2-3 weeks on average. The artist is 23 years old. |
Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone can see the numbers that are NOT on their own forehead. Call the three numbers x,y,z. They wish to determine if x+y+z is divisible by 1,000,000,000,000. There is an easy solution: Alice can just say Bob, your number is .... This would take 13 digits of communication. Can they do better?Chandra, Furst, and Lipton showed that if instead of 1,000,000,000,000 was replaced by 2n, and if n is large, then do this in roughly \sqrt n bits. They were more interested in the k-party lower bound of ω(1) since this leads to lower bounds on branching programs. (NOTE: They studied a variant of the the problem above, but everything they did applies hear also.) See their paper or my writeup for JUST the upper bound or my writeup of the upper and lower boundand its application to branching programs for more information.
My 11-year old daughter talked about using straight lines and angles to improve her mini-golf game. That reminded me of the billiard ball scene in a Donald Duck math movie I saw many times over during my grade school years. Off to YouTube where we watched Donald in Mathmagic Land which coincidentally turns fifty years old this month.
Holds up pretty well after fifty years though the modern music, art, architecture and technology aren't so modern any more. Catch the Turing machine (reel-to-reel computer) near the end.
It was this movie and a Time-Life book on mathematics (which had a really cool chapter on probability) that got me excited by the fun of math which, of course, helped shape my future academic career.
The movie has a scene where Donald tries to open some locked doors that the narrator says represents knowledge yet to be discovered. Cool to think that I have now witnessed many of those door opened, some with my own hands.
> {-# LANGUAGE MultiParamTypeClasses,FlexibleInstances,FunctionalDependencies,GeneralizedNewtypeDeriving #-}
> module Main where
> import Data.HashTable
> import Data.List as L
> import Data.Int
> import Data.Array
> import GHC.Arr
> import qualified Data.Map as M
> import Control.Monad
> infixl 5 .+
> infixl 6 .*
> data I = A | B | C | D deriving (Eq,Ord,Show,Ix,Enum)
> c' (a,b,c,d) = hashString ("C" ++ show (a,b,c,d))
Memoisable type class with a memo method. So I'll be using c instead of c':symmetrise function. The idea is that the 4 bonds coming out from (singly-bonded) carbon can be thought of as lying at the corners of a tetrahedron.
c (i,j,k,l) == c (j,i,l,k). We can enforce this by summing over all 24 permutations of the arguments compatible with this symmetry, also known as A4. So a4 lists all of these permutations:
> a4 (i,j,k,l) = [
> (i,j,k,l),
> (j,i,l,k),
> (k,l,i,j),
> (l,k,j,i),
> (i,k,l,j),
> (i,l,j,k),
> (k,j,l,i),
> (l,j,i,k),
> (j,l,k,i),
> (l,i,k,j),
> (j,k,i,l),
> (k,i,j,l)
> ]
symmetrise performs the summation:
> symmetrise group f x = sum (map f (group x))
> h = memo $ \a -> hashString ("H" ++ show a) .* return ()
> s2 (i,j) = [ (i,j), (j,i) ]
> o' (a,b) = hashString ("O" ++ show (a,b))
> o = memo $ \x -> symmetrise s2 o' x .* return ()
> bond :: V Int32 I
> bond = return A .+ return B .+ return C .+ return D
> h2 = simp $ do
> i <- bond
> h ! i
> h ! i
i <- bond makes i a bond which we then attach to two hydrogen atoms. Evaluating h2 will give us the hash for hydrogen gas.
> h_ :: V Int32 I
> h_ = do
> m <- bond
> h ! m
> return m
ch2_ accepts one bond and returns another. Once memoised it is, in effect, just a 4x4 matrix and can be used to rapidly build chains.
> ch2_ = memo $ \i -> simp $ do
> k <- bond
> l <- bond
> m <- bond
> h ! l
> h ! m
> c ! (i,k,l,m)
> return k
> alkyl_ 0 = h_
> alkyl_ n = simp $ do
> i <- alkyl_ (n-1)
> ch2_ ! i
> alkane n = simp $ alkyl_ n >>= (h ! )
> methane = alkane 1
> oh = memo $ \i -> simp $ do
> j <- bond
> h ! j
> o ! (i,j)
> ethanol = simp $ do
> i <- alkyl_ 2
> oh ! i
> doubleBond :: V Int32 (I,I)
> doubleBond = simp $ do
> i <- bond
> j <- bond
> return (i,j)
symmetrise if we wanted twistable bonds.
> c_c = memo $ \(i,j,k,l) -> simp $ do
> (m,n) <- doubleBond
> c ! (i,j,m,n)
> c ! (m,n,k,l)
> ethene = simp $ do
> i <- h_
> j <- h_
> k <- h_
> l <- h_
> c_c ! (i,j,k,l)
> ch3_ = simp $ do
> l <- h_
> ch2_ ! l
> propene = simp $ do
> j <- ch3_
> i <- h_
> k <- h_
> l <- h_
> c_c ! (i,j,k,l)
> cisbut2ene = simp $ do
> i <- ch3_
> j <- h_
> k <- ch3_
> l <- h_
> c_c ! (i,j,k,l)
> transbut2ene = simp $ do
> i <- h_
> j <- ch3_
> k <- ch3_
> l <- h_
> c_c ! (i,j,k,l)
> cisbut2ene' = simp $ do
> i <- h_
> j <- ch3_
> k <- h_
> l <- ch3_
> c_c ! (i,j,k,l)
> _2methylpropene = simp $ do
> i <- ch3_
> j <- ch3_
> k <- h_
> l <- h_
> c_c ! (i,j,k,l)
> _2methylpropene' = simp $ do
> i <- h_
> j <- h_
> k <- ch3_
> l <- ch3_
> c_c ! (i,j,k,l)
> ring1 (p,q,r,s,t,u) = simp $ do
> i <- bond
> j <- bond
> k <- bond
> c_c ! (j,q,i,p)
> c_c ! (i,u,k,t)
> c_c ! (k,s,j,r)
> ring = memo $ \(p,q,r,s,t,u) -> simp $ ring1 (p,q,r,s,t,u) .+ ring1 (q,r,s,t,u,p)
> phenyl = memo $ \p -> simp $ do
> q <- h_
> r <- h_
> s <- h_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> benzene :: V Int32 ()
> benzene = simp $ do
> i <- bond
> phenyl ! i
> h ! i
> phenol :: V Int32 ()
> phenol = simp $ do
> i <- bond
> phenyl ! i
> oh ! i
> toluene :: V Int32 ()
> toluene = simp $ do
> i <- ch3_
> phenyl ! i
> toluene' :: V Int32 ()
> toluene' = simp $ do
> p <- h_
> q <- h_
> r <- h_
> s <- ch3_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> toluene'' :: V Int32 ()
> toluene'' = simp $ do
> p <- h_
> q <- h_
> r <- ch3_
> s <- h_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> _1_2_dimethylbenzene = simp $ do
> p <- ch3_
> q <- ch3_
> r <- h_
> s <- h_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> _1_3_dimethylbenzene = simp $ do
> p <- ch3_
> q <- h_
> r <- ch3_
> s <- h_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> _1_4_dimethylbenzene = simp $ do
> p <- ch3_
> q <- h_
> r <- h_
> s <- ch3_
> t <- h_
> u <- h_
> ring ! (p,q,r,s,t,u)
> _1_5_dimethylbenzene = simp $ do
> p <- ch3_
> q <- h_
> r <- h_
> s <- h_
> t <- ch3_
> u <- h_
> ring ! (p,q,r,s,t,u)
> main = do
> print $ "toluene = " ++ show toluene
> print $ "toluene' = " ++ show toluene'
> print $ "toluene'' = " ++ show toluene''
> print $ "_1_2_dimethylbenzene = " ++ show _1_2_dimethylbenzene
> print $ "_1_3_dimethylbenzene = " ++ show _1_3_dimethylbenzene
> print $ "_1_4_dimethylbenzene = " ++ show _1_4_dimethylbenzene
> print $ "_1_5_dimethylbenzene = " ++ show _1_5_dimethylbenzene
> class Memoisable ix where
> memo :: (ix -> a) -> Array ix a
> instance Memoisable I where
> memo f = array (A,D) [(i,f i) | i <- [A .. D]]
> instance Memoisable (I,I) where
> memo f = array ((A,A),(D,D)) [(i,f i) |
> p <- [A .. D],
> q <- [A .. D],
> let i = (p,q) ]
> instance Memoisable (I,I,I,I) where
> memo f = array ((A,A,A,A),(D,D,D,D)) [(i,f i) |
> p <- [A .. D],
> q <- [A .. D],
> r <- [A .. D],
> s <- [A .. D],
> let i = (p,q,r,s) ]
> instance Memoisable (I,I,I,I,I,I) where
> memo f = array ((A,A,A,A,A,A),(D,D,D,D,D,D)) [(i,f i) |
> p <- [A .. D],
> q <- [A .. D],
> r <- [A .. D],
> s <- [A .. D],
> t <- [A .. D],
> u <- [A .. D],
> let i = (p,q,r,s,t,u) ]
Data.Array:
> instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6) => Ix (a1,a2,a3,a4,a5,a6) where
> range ((l1,l2,l3,l4,l5,l6),(u1,u2,u3,u4,u5,u6)) =
> [(i1,i2,i3,i4,i5,i6) | i1 <- range (l1,u1),
> i2 <- range (l2,u2),
> i3 <- range (l3,u3),
> i4 <- range (l4,u4),
> i5 <- range (l5,u5),
> i6 <- range (l6,u6)]
> unsafeIndex ((l1,l2,l3,l4,l5,l6),(u1,u2,u3,u4,u5,u6)) (i1,i2,i3,i4,i5,i6) =
> unsafeIndex (l6,u6) i6 + unsafeRangeSize (l6,u6) * (
> unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
> unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
> unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
> unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
> unsafeIndex (l1,u1) i1)))))
> inRange ((l1,l2,l3,l4,l5,l6),(u1,u2,u3,u4,u5,u6)) (i1,i2,i3,i4,i5,i6) =
> inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
> inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
> inRange (l5,u5) i5 && inRange (l6,u6) i6
Int32 isn't a field.
> swap (x,y) = (y,x)
> class Num k => VectorSpace k v | v -> k where
> zero :: v
> (.+) :: v -> v -> v
> (.*) :: k -> v -> v
> (.-) :: v -> v -> v
> v1 .- v2 = v1 .+ ((-1).*v2)
> data V k a = V { unV :: [(k,a)] } deriving (Show)
> reduce x = filter ((/=0) . fst) $ fmap swap $ M.toList $ M.fromListWith (+) $ fmap swap $ x
> simp (V x) = V (reduce x)
> instance (Ord a,Num k) => Eq (V k a) where
> V x==V y = reduce x==reduce y
> instance (Ord a,Num k,Ord k) => Ord (V k a) where
> compare (V x) (V y) = compare (reduce x) (reduce y)
> instance Num k => Functor (V k) where
> fmap f (V as) = V $ map (\(k,a) -> (k,f a)) as
> instance Num k => Monad (V k) where
> return a = V [(1,a)]
> x >>= f = join (fmap f x)
> where join x = V $ concat $ fmap (uncurry scale) $ unV $ fmap unV x
> scale k1 as = map (\(k2,a) -> (k1*k2,a)) as
> instance Num r => MonadPlus (V r) where
> mzero = V []
> mplus (V x) (V y) = V (x++y)
> instance (Num k,Ord a) => VectorSpace k (V k a) where
> zero = V []
> V x .+ V y = V (x ++ y)
> (.*) k = (>>= (\a -> V [(k,a)]))
> e = return :: Num k => a -> V k a
> coefficient b (V bs) = maybe 0 id (L.lookup b (map swap (reduce bs)))
I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a swimming pool accident at his home. He will be remembered by the large number of professional colleagues, faculty colleagues, and students whose education and lives have been enriched tremendously by his.
A song about Mandelbrot Sets, although one of the comments on it claims that the song is actually about Julia sets. The person who send it was amused that there is a curse word in it. But he's young and easily amused--- he's 32.
Here is a sketch of Moser's proof written as a Kolmogorov complexity argument. This is not the full Lovász Local Lemma but captures the main principle.
Theorem: Suppose we have a k-CNF formula φ with n variables and m clauses and each clause shares a variable with at most r other clauses. There is a constant d such that if r 2k-d then φ is satisfiable. Moreover we can find that assignment in time polynomial in m and n.
Here's the algorithm:
Solve(φ)
Pick a random assignment of φ
While there is an unsatisfiable clause C
Fix(C)
Fix(C)
Replace the variables of C with new random values
While there is clause D that shares a variable with C that is not
satisfied
Fix(D)
Assume Fix(C) always terminates. Every clause that was satisfied before we called Fix(C) will still remain sastisfied and C will also now be satisfied. So Solve makes at most m calls to Fix.
We need to show all the Fix(C) terminate. Suppose the algorithm makes at least s Fix calls including all the recursive ones. We will show s is bounded and thus the algorithm terminates.
Fix a Kolmogorov random string x of length n+sk (random relative to φ, k, s, r, m and n) and assume the algorithm uses the first n bits as the initial assignment and k bits each to replace the variables in each Fix call.
If we know which clause is being fixed, we know the clause is violated so we know all the bits of this clause and thus we learn k bits of x. We then replace those bits with another part of x.
So we can describe x by the list of clauses we fix plus the remaining n bits of the final assignment. We can describe the C such that Fix(C) is called by Solve by m log m bits and the remaining fixed clauses by log r + O(1) bits because either it is one of r clauses that intersects the previous clause or we indicate the end of a recursive call (keeping track of the recursion stack).
So we must have m log m + s(log r+O(1))+n ≥ n+sk or s(k-log r-O(1)) ≤ m log m.
To show s is bounded, we need k-log r-O(1) to be positive or r2k-d for some constant d.
Note this in fact shows s = O(m log m) so the algorithm runs in polynomial time. We choose the x randomnly which with high probability will be Kolmogorovly random. QED
In the talk, Moser gives the bound r2k-3 and in follow-up work with Gábor Tardos shows r2k/e (e = 2.71…) which is the best that comes out of the original Lovász Local Lemma.
What do these depict?
Here are two others. Different data source, different point in time, but what are they?
They are all linked in pairs - one coloured and one black linked together. They are not sports related. And they are taken from real world data. The colours are relevant and constitute a hint in their own right.
I missed the Valiant celebration but it brought a large number of senior theorists who don't often attend STOC/FOCS. I enjoyed seeing and talking with them. Still, despite a relatively easy to reach location (say compared with last year's Victoria), STOC only attracted about 260 attendees, nearly half students. We just don't get draw many non-local attendees who don't have papers in the conference. Though David Johnson told me he's attended every STOC since the early 70's.
I don't attend many talks at STOC, I prefer to hang in the hallways chatting with people, about research, politics, gossip and baseball. The talks I did attend usually had about five or so good minutes of motivation and results followed by technical details for experts in that particular area. That's probably the right way to give those talks but I was rarely one of those experts.
And then I see a talk as amazing as Moser's and I realize: This is why I love theory.
These are the slides and the extended abstract from my MSFP 2008 talk. Apparently, I forgot to publish them online. There is a discussion on the Agda mailing list to which the talk is somewhat relevant, so I am publishing now.
Abstract: Realizability is an interpretation of intuitionistic logic which subsumes the Curry-Howard interpretation of propositions as types, because it allows the realizers to use computational effects such as non-termination, store and exceptions. Therefore, we can use realizability as a framework for program development and extraction which allows any style of programming, not just the purely functional one that is supported by the Curry-Howard correspondence. In joint work with Christopher A. Stone we developed RZ, a tool which uses realizability to translate specifications written in constructive logic into interface code annotated with logical assertions. RZ does not extract code from proofs, but allows any implementation method, from handwritten code to code extracted from proofs by other tools. In our experience, RZ is useful for specification of non-trivial theories. While the use of computational effects does improve efficiency it also makes it difficult to reason about programs and prove their correctness. We demonstrate this fact by considering non-purely functional realizers for a Brouwerian continuity principle.
Download: msfp2008-slides.pdf, msfp2008-abstract.pdf
I have a dyslexic 9 year old and I wish to find out if your program can benefit him. I have tried Math-U-See and it became too boring or frustrating for him. I have tried various other programs in hope of not overwhelming him. He has completed the delta Math U See level but I feel needs more work on long division. He simply gets very frustrated with it, as the length of time and knowing where to place number due to dyslexia. Is your curriculum a spiral curriculum? Any suggestions would help.One of my books from the Blue Series goes through long division in several small steps: Math Mammoth Division 2
> {-# LANGUAGE MultiParamTypeClasses,FunctionalDependencies,FlexibleInstances #-}
> module Main where
> import qualified Data.Map as M
> import Control.Monad
> infixl 5 .+
> infixl 6 .*
> data Space = X | Y | Z deriving (Eq,Show,Ord)
V Float Space, for example:
> u,v,w :: V Float Space
> u = return X .- return Y
> v = return X .+ 2.* return Y
> w = return Y .- return Z
() -> V Float Space instead.
> cup :: (Space,Space) -> V Float ()
> cup (i,j) = case (i,j) of
> (X,X) -> return ()
> (Y,Y) -> return ()
> (Z,Z) -> return ()
> otherwise -> 0 .* return ()
> vdotw = do
> i <- v
> j <- w
> cup (i,j)
In other words, turning a vector v upside down turns it into a dual vector that takes w to the dot product of v and w. Here's some code for making the dual of v.
> dual :: V Float Space -> Space -> V Float ()
> dual v i = do
> j <- v
> cup (i,j)
> cross :: (Space,Space) -> V Float Space
> cross (X,Y) = return Z
> cross (Y,Z) = return X
> cross (Z,X) = return Y
> cross (Y,X) = (-1) .* return Z
> cross (Z,Y) = (-1) .* return X
> cross (X,Z) = (-1) .* return Y
> cross _ = mzero
> trident :: (Space,Space,Space) -> V Float ()
> trident (i,j,k) = do
> l <- cross (i,j)
> cup (l,k)
> cap :: () -> V Float (Space,Space)
> cap () = return (X,X) .+ return (Y,Y) .+ return (Z,Z)
> cupcap i = do
> (j,k) <- cap ()
> cup (i,j)
> return k
cupcap to X, Y and Z you'll see it has exactly the same effect as return, which does indeed represent the identity.cup and cap were implemented it would be impossible for k to be a copy of i. If you follow the flow of information through that code then i disappears into cup and k is read from cap without it seeing i. If we read from top to bottom we can think of cap as emitting a pair of objects and of cup as absorbing two. There is no way that any information about i can be communicated to k. But in the vector space monad, k can depend on i. As I've mentioned a few times over the years, the universe is described by quantum mechanics which can be described using the vector space monad. Amazingly the above piece of code, or at least something like it, can be physically realised in terms of particles. It describes a process that is fundamentally quantum, and not classical. In fact, Coecke shows that this is a precursor to quantum teleportation in section 3c of this paper. You could also think in terms of information about i being sent back in time through the cap. That's the idea behind this paper on Effective Quantum Time Travel.)
> fork () = do
> (i,j) <- cap ()
> (k,l) <- cap ()
> m <- cross (j,k)
> return (i,l,m)
> a :: Space -> V Float Space
> a X = 2 .* return X
> a Y = return Z
> a Z = (-1) .* return Y
> b :: Space -> V Float Space
> b l = do
> (i,j) <- cap ()
> k <- a j
> cup (k,l)
> return i
> det a = do
> (i,j,k) <- fork ()
> i' <- a i
> j' <- a j
> k' <- a k
> (1/6.0) .* trident (i',j',k')
> swap (x,y) = (y,x)
> class Num k => VectorSpace k v | v -> k where
> zero :: v
> (.+) :: v -> v -> v
> (.*) :: k -> v -> v
> (.-) :: v -> v -> v
> v1 .- v2 = v1 .+ ((-1).*v2)
> data V k a = V { unV :: [(k,a)] }
> instance (Num k,Ord a,Show a) => Show (V k a) where
> show (V x) = show (reduce x)
> reduce x = filter ((/=0) . fst) $ fmap swap $ M.toList $ M.fromListWith (+) $ fmap swap $ x
> instance (Ord a,Num k) => Eq (V k a) where
> V x==V y = reduce x==reduce y
> instance (Ord a,Num k,Ord k) => Ord (V k a) where
> compare (V x) (V y) = compare (reduce x) (reduce y)
> instance Num k => Functor (V k) where
> fmap f (V as) = V $ map (\(k,a) -> (k,f a)) as
> instance Num k => Monad (V k) where
> return a = V [(1,a)]
> x >>= f = join (fmap f x)
> where join x = V $ concat $ fmap (uncurry scale) $ unV $ fmap unV x
> scale k1 as = map (\(k2,a) -> (k1*k2,a)) as
> instance Num r => MonadPlus (V r) where
> mzero = V []
> mplus (V x) (V y) = V (x++y)
> instance (Num k,Ord a) => VectorSpace k (V k a) where
> zero = V []
> V x .+ V y = V (x ++ y)
> (.*) k = (>>= (\a -> V [(k,a)]))
> e = return :: Num k => a -> V k a
> coefficient b (V bs) = maybe 0 id (lookup b (map swap (reduce bs)))
My good friend Antony Eagle has a survey on causation that he'd like people to have a look at. The link is here:
http://www.surveymonkey.com/s.aspx?sm=flm10kfdTBAcPUGy1hay9A_3d_3d
x-posted at Thoughts, Arguments and Rants
I started fiddling around with R again, and ended up playing with a zipcode database.
So, first I downloaded the zipcode database at Mapping Hacks, and unpacked the zipfile in my working directory.
Then, I loaded the data into R
So, now I have an R frame containing a lot of US cities, their geographical coordinates, and their zip codes. So we can start playing with the plot command! After rooting around a bit, I ended up settling on the smallest footprint plot dot I could make R produce, by setting the option pch=20 in the plot options. Hence, I ended up with a command basically like this:
where the +1 after the modulus is to make even 0-values plot, and the cex parameter sets the point size to something small and pretty.
We can continue this, tweaking the divisor to extract all the other digits of the zip code, and we end up getting:
and the result
and the result
and the result
and finally
and the result
And then, of course, we can zoom in on data too. So we can do things like extracting Californian zip codes
to get
or, we could extract New York zip codes:
or even extract, say, the zip codes starting with 10 or 11, covering New York City and surroundings and take a closer look
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 July 03, 2009 09:24 PM 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 Computational Complexity Diary of a Black Mathematician Homeschool Math Blog LogBlog Logicomp Mathematics - Topix.net Mathematics and Computation Michi's blog Mostly Mathematics 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