This past Sunday, did you see hundreds of photos from the People’s Climate March posted on your friends’ Facebook and kick yourself for having a lazy afternoon on your couch (as I kind of did)?

The New York Times reported that, on September 21, approximately 311,000 people participated in the March in New York City. The article said that the number was “… provided by 35 crowd spotters and analyzed by a mathematician from Carnegie Mellon University…”

There seem to be at least a few different ways of counting crowds, many of which use a basic “area times density” principle. They include the classic technique developed in the 1960s called the Jacobs Method, and updated, more accurate methods such as Yip and Watson’s.

While 311,000 was more than enough to make me wonder why I didn’t join this historic event, the event’s organizer claims that nearly 400,000 marched. There is no way to know whether this discrepancy comes from simple errors, or public relations motives. Or is there?

Professors: Do you think you can use this topic in any of your math classes? If so, in which course and how?

(Photo courtesy of Professor Jonathan Cornick at QCC, who was one of those Facebook friends)

I am an Associate Professor in the Mathematics and Computer Science Department at Queensborough Community College, and I have spent the last six years working on improving remedial mathematics.

When I started at QCC in 2007, students either placed into a semester long elementary algebra course, or a semester long arithmetic course after which, if they passed, they were required to take the elementary algebra course. The majority of students coming to QCC placed into one of these courses. Success rates were very low – for example only 3% of students placing into arithmetic graduated with an Associates degree within six years, only 10% of them even exited remediation, and in general passing rates in elementary algebra were consistently 35-40%.

I have been involved in several evidence-based reforms to address the low success rates of students who place into remedial mathematics. Each step the changes have been directed by a growing body of peer reviewed research, and by careful analysis of local statistical data.

In 2009 the QCC math department created a compressed 4-week, 20-hour version of the arithmetic course. This course was successful in the sense that students passed at a much higher rate, despite having the same curriculum and exit requirements as the traditional course. However, later analysis revealed that these students weren’t passing elementary algebra at a greater rate than before. The arithmetic course(s) seemed mainly to serve as an obstacle to student success. In Spring 2013 the department voted to eliminate the arithmetic course completely for a variety of reasons.

Together with my colleagues G. Michael Guy and Karan Puri, we studied the effect of the course elimination and found that students who would previously have placed into arithmetic were not adversely affected in the rate at which they passed elementary algebra. This study has been published in MathAMATYC Educator.

Of course, we are under no illusion that we have magically solved the issue of weak arithmetic skills in some of our students, but we believe that an arithmetic course is not the solution to this issue. Students, who learn an arithmetic skill in one course, aren’t likely to remember it 4-6 months later when it’s required in algebra if they weren’t given a context in the first place.

However, whether students take arithmetic or not, exit rates from remedial mathematics at QCC remain disturbingly low in the 35-40% range. In an attempt to address thiswe wrote an elementary algebra book in which we contextualize arithmetic skills and introduce them “just in time”. For example, we start with linear equations, which only require positive integer operations to solve, then review signed numbers, and then move on to linear equations with negative number operations. Initial results have been promising, in a study involving six instructors using this textbook students were nearly twice as likely to pass the course as opposed to a control group taught be instructors using the standard departmental text.

Our emphasis is on rethinking pedagogy and using time more effectively for student centered problem solving rather than shifting the issue to a lower course.

My research, supported this year by a Chancellor’s Research Fellowship for Community Colleges, will focus on these questions:

1. How do students who would have formerly been placed into arithmetic perform in their credit math course(s)?
2. How do students who take remedial algebra in classes with our contextualized textbook and student centered problem solving pedagogy perform in subsequent credit math course(s)?
3. How do various attributes and attitudes influence student success, and what can we do inside and outside the classroom to support those which have a positive effect, and change those which have a negative effect?

In Spring 2014, Interim Chancellor Kelly awarded 19 “Chancellor’s Research Fellowships” to faculty at CUNY’s community colleges through a highly competitive process.  These fellowships fund research in many disciplines during the 2014-2015 academic year.  Three of the Fellows are mathematicians.  Luis Fernandez from Bronx Community College submitted a proposal regarding the curvature of harmonic surfaces in spheres. Uma Iyer, also from Bronx Community College, will examine representations of algebras of quantum differential operators.  Queensborough Community College’s Jonathan Cornick will engage in a longitudinal study of remedial mathematics reform.  Congratulations to these faculty.

Stay tuned!  Professor Cornick will keep CUNYMath blog readers apprised of his research.

Calculus Boot Camp, an initiative of Interim Chancellor William Kelly, has launched at six CUNY campuses.  In July and August 2014, hundreds of students across Baruch College, Brooklyn College, City College, LaGuardia Community College, Lehman College and NYC College of Technology will participate in free workshops on campus.  Designed to enhance  the skills of students between their spring semester of Pre-Calculus and fall semester of Calculus, Boot Camp aims to give participants an advance look at the material they will cover for credit in a few short weeks. The program is sponsored by the CUNY Central Office of Academic Affairs, and will include an evaluation component to gauge its effects.

Math faculty teaching the workshops also serve as campus coordinators for the program.  Special thanks to Professors Peter Gregory, Jeff Suzuki, Matthew Auth, Mahdi Majidi-Zolbanin, Joseph Fera and Satyanand Singh.  Follow along at #CalculusBootcamp

Last semester I taught a large section of Calculus I. There were 124 students in the class. Teaching a large class is not for everyone, but if you are so inclined, it can be a rewarding experience provided you pay attention to certain details.

Teaching a large class of over a hundred students requires a good deal of management skill. This sort of management isn’t a one-time thing like preparing lecture notes and reusing them. No, this sort of management is an integral component of teaching large classes. There’s management of the students and management of the graduate teaching assistants. If management is not your cup of tea, then it’s best to stick to the usual class maximum of 35 students.

At least one teaching assistant is indispensable, at the very least to help with monitoring exams and collecting and returning homework, quizzes, and exams. Otherwise too much class time will be spent on these sorts of administrative tasks. Liang Zhao served as teaching assistant for my Calculus I class last semester. He did a great job. The students appreciated our seamless efficiency.

There are many ways to assign responsibilities to a teaching assistant. I assigned grading of homework and quizzes (25% of the grade) to Liang. In my classes homework and quizzes are graded generously with relaxed deadlines; there is no reason why everyone cannot get a high score.

I also organized two informal recitation sessions per week. These sessions scheduled from 8:00 am – 9:00 am on Tuesdays and Thursdays quickly became popular especially since Liang is a good instructor. These sessions had the effect of not only helping students to finish their homework, but also of making sure they were on time. Students got into the habit of coming well before 9:00 am for the 9:00 am class. Punctuality is a big deal in a large class. Otherwise there will be students strolling in at all times. It must be enforced through a combination of incentives and consequences. It is an ongoing management issue.

Together, Liang and I worked hard to make this class a success, considerably over what was expected of us. Our reward was that things went well. It would be very easy to spend a lot of time and still have all sorts of problems leading to a frustrating experience. Fortunately our strategies were effective.

I graded the exams (2 tests and a final each 25% of the grade). If I didn’t do this, I wouldn’t have a good sense of what the students were learning. I got to know the students and was able to give them one-on-one attention – something that is hard to do in a large class. I am not advocating this particular strategy as it is extremely time-consuming, merely noting that I found it effective at communicating my leadership style.

Anonymity in numbers is an issue in a large class. Some interesting things occur when the students think the professor does not know Jill from Jane or Fred from Frank.

One such thing is changing test answers and asking for a re-grade under the assumption the professor made a mistake. My tests are not multiple-choice tests and I give partial credit. It is possible to overlook a correct step here and there when grading so many exams. My solution was to photocopy the exams before returning. Yes, all 124 of them. These are the organization and management issues I was talking about. It’s an ongoing thing throughout the semester. The plus side is that I have a wealth of data that I can analyze at my convenience.

When taking a test sitting so close to each other, it is hard not to accidently look at a neighbor’s test inches away. This made everyone uncomfortable. I handled this issue by using two large classrooms for exams, one monitored by me and the other by the TA. Students were able to sit comfortably at a respectable distance from each other. For the final exam all the students were in the auditorium that seats 260. I thought this was better than splitting up the class.

Room size can become an issue. I had 124 students in a 130 seat classroom. If I could make one suggestion, it would be to reduce the maximum size of the class to 110 so as to fit comfortably in the many large classrooms that seat 130 to 160. The seats are too tightly crammed together making it difficult to get in and out when filled to capacity. I noticed that students preferred sitting on the floor and the steps rather than sitting so very close to each other.

This is especially important in a math class because a larger auditorium may be problematic. I don’t think there is any effective substitute for writing on the board while explaining math. I also think a technology-enhanced lecture is good and I used the computer and projector often. But writing on the board is a basic strategy for teaching math. If the classroom is too large, like for example, the 260 seat auditorium, then students in the back cannot see the board – there is only so big we can write.

It would be a mistake to teach a large class thinking one can do the same amount of work or a little more and get double teaching credits. It is more work than teaching two regular size classes (for a maximum of 70 students). For the administration, it is three sections for the price of two. For faculty it frees up some in-house teaching hours for advising graduate and undergraduate students and mentoring teaching assistants. This is especially so for faculty with limited in-house teaching hours, whether the limitation is due to grant commitments, commuting difficulties or something else. It could be a win-win situation for both faculty and administrators.

In my next post I will talk about the data I collected and the results of my analysis.

There has been some talk in the news recently that the security provided by the RSA encryption algorithm isn’t as secure as it used to be.

RSA is an acronym standing for Rivest, Shamir, and Adleman, the individuals who designed the algorithm at MIT in 1977.

Rivest, Shamir and Adleman

An equivalent system was developed by British mathematician Clifford Cocks in 1973, though at the time he was working for a clandestine branch of the government, and his work went unattributed for many years.

Clifford Cocks

The RSA algorithm is one of the cryptographic workhorses of the internet, helping to put the “s” in “https” on the websites we use every day.  Through ingenious means, which we won’t discuss here, it is also used to produce digital signatures, which guarantee that messages originate from their specified sources.

The article linked above, concerning looming insecurities in RSA, discusses a recent talk delivered by Alex Stamos at the annual Black Hat conference in Las Vegas.  From the article it is difficult to fathom how dire the crisis might be.  It’s said that Stamos is disconcerted by recent progress made by French mathematician Antoine Joux on the discrete logarithm problem.  There is no comment from Joux, whose word I would find more definitive.  How certain can we be that the alarm isn’t an illusion?

Those things will become more clear in coming weeks no doubt.  But what is the discrete logarithm problem, and how does it relate to RSA?

We should start with a review of the ordinary logarithm function, invented by the Scottish wizard Napier in the 17th century. We then give a short description of modular arithmetic, define the discrete logarithm problem, and review RSA.  Finally, we’ll see how all these fit together, and why the ability to compute discrete logarithms quickly challenges current security protocols.

A logarithm is a function which takes two positive real numbers, a base together with an input and returns the number such that . In notation we express this by .

The fact that there is such a number is interesting in itself.  The existence of can quickly be confirmed by examining a graph of the exponential function.  The following figure is for , though for other values of the figure is essentially the same.  Note that for any output (on the axis) there is an input (on the axis) such that the function strikes the output with the input.  This justifies the definition of the logarithm.

The graph of the curve described by y = 2^x

To understand the discrete logarithm, it is necessary to understand the discrete context.  Here we are not concerned with real numbers, but rather with integers (whole numbers).  In fact, we are only concerned with the numbers for a fixed integer .  We can do arithmetic in this finite realm provided we are willing to “wrap around” when our sums an products go out of scope.  The exact nature of what happens is discussed in this introductory article from the Khan Academy.  If you would like something more serious, the article by Gauss himself is not difficult, and uses (in fact introduces) all the modern notation.  Amazingly I cannot find an English edition of Disquisitiones Arithmeticae online, and so I refer the reader to the excerpts found in the collection God Created the Integers.

To give a few fast examples, we write

to mean that if we were to consider stones and count them out in groups of 4, in the last pile we would have a single stone.  We call 1 the residue of 25 modulo 4. Note that if we were to take 5 stones and count them out in groups of 4, then in the last pile we would have only 1 stone.  That is, the residue of 5 mod 4 is already 1.  Note also that in this case the product of the residues is the residue of the product.  In other words, using C++ notation,

because .

In fact this is true in general, and explains many of the properties of numbers we learn in grade school.  For instance we learn that a number is divisible by 3 if and only if its digits sum to three.  I will use modular arithmetic to show why this is true for the arbitrary example of 2349. First expand using the definition of a decimal number.

Now note that and so the same is true for any power of 10.  Thus .

Now is divisible by three if and only if .  That is, it is equivalent to the condition that the sum of the digits is also 0 mod 3, or in other words that the sum of the digits is divisible by 3.  This gives something of the flavor of discrete arithmetic.

What should a logarithm be in the discrete context?  We can use the old definition, with an additional twist.  For numbers and in define the discrete logarithm (base ) of to be the number in such that .  For instance, because we know that , it follows that the discrete logarithm of 10 base 11 mod 17 is 5.

Again, we have the question of whether the logarithm is well defined.  Is it the case that for any choice of and , the integer exists such that ?  The answer is no — you should find it easy to produce a counter example.  Also, unlike the continuous cases, the discrete exponential function is not one-to-one.  This means that the uniqueness of is also an issue.

In group theoretic terms, the base now has to be a generator of the multiplicative group of integers mod in order for the definition of logarithm to make sense.  These details don’t matter for a rough discussion of discrete logs as they apply to cryptography.

Questions of efficient means of computing discrete logarithms arise in many cryptographic systems, but we will focus our attention of RSA.  At this point we need some account of what RSA is, for which I have written the this using the iPython notebook to produce an annotated example.

After following the link and diligently reading, you must now know that the crux of the RSA algorithm is the decryption step .   Can we cast this as a question about a logarithm?  Recall from the RSA example that the secret parts of the above equation are and .  The ciphertext is public knowledge, as is the modulus .  But anyone is free to encrypt a message using any public key.  This means that we can pick , and so we can know that value too.  Thus the real mystery is , the private exponent.

To find , what we need to know is:  To what power must be raised in order to be congruent to modulo ?

In other words, to crack RSA we want to know the discrete logarithm of base modulo .

For this reason, if Joux or his colleagues ever do find a fast method for computing discrete logarithms, the current implementations of many common cryptographic systems, including systems for producing digital signatures, will become obsolete.

This is not the only way to break RSA.  It seems like it should be easier in fact to crack RSA for a particular message rather than find and unravel the whole system.  To do this, imagine that the message is produced not by us but by someone communicating with the victim.  To recover we must solve for it in the equation

,

in which it is the only unknown.  This is not a logarithm problem, but is instead the problem of discrete root extraction.  In fact this problem has its own name — it is called the RSA problem.  Obviously no practical means is yet known for solving this problem either.

RSA could fall because of advances in the science of number factoring.  While this has not yet led to the gelding of RSA as far as anyone is saying, still the speed with which numbers can be factored has improved in dramatic and unexpected ways.

Shortly after RSA was announced, the popular mathematics writer Martin Gardner asked Rivest, Shamir, and Adleman for an encrypted message with which he could tease his readers.  They agreed, and produced an encoded message using a 129-digit public key.  The value of in the key was:

The prize for producing a solution was $100.  Rivest calculated, based on mathematical technology existing at the time, that factoring this number would require 40 quadrillion years.  This figure assumed a machine capable of performing 1 billion modular multiplications per second, which seems to have been achieved at the PC level only in 2009.

As this article explains, Rivest’s figures were off by many orders of magnitude, but not because he underestimated the growth in computing power.  Rather, he was overly optimistic about innovations in factoring large numbers, in particular sophisticated variants of the quadratic sieve. This article by Pomerance outlines some of the history.

For those who are curious about the solution to Gardener’s puzzle, it may interest you to know that (as a team of hackers found in 1994)

 =

The message which was encoded read: THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

I am indebted to Julian Brown’s book The Quest for the Quantum Computer for this anecdote.  Incidentally Brown’s book is a good starting place for reading about that other perennial threat to our online security: quantum computing.

A year or so ago I stumbled across Reuben Hersh’s “Under-represented Then Over-represented: A Memoir of Jews in American Mathematics” in the pages of a recent Best Writing on Mathematics volume.

That article describes the arc of Jewish mathematical history in the time of WW II and afterwards, featuring some personal recollections acquired during Hersh’s tenure as a student at the Courant Institute.  This was my first encounter with the story of the effect that the Nazi regime had on mathematical culture in Germany, perhaps best summarized by Hilbert’s famous response to Bernhard Rust’s query about the state of mathematics at Göttingen under fascism:  “There is really none anymore.”

A fascinating prequel to Hersh’s observations and memories can now be found at an exhibit on display at the Center for Jewish History on 16th Street.  Transcending Tradition: Jewish Mathematics in German-Speaking Academic Culture will be available from the time of this writing until January 2014.  Admission is free.

The exhibit tells its story in three epochs, beginning in years previous to 1871, following through the days of the Wilhelmine Empire, and focusing at last on the days of the Weimar Republic (1919-1933) and the immediate aftermath.

There are many names mentioned, but to give a sampling from each time period:

pre 1871:  Leopold Kronecker (Berlin), Rudolph Lipschitz (Breslau), Carl Gustav Jacob Jacobi (Königsberg).

1871-1919: Max Noether (Heidelberg), Felix Hausdorff (Greifswald), Hermann Minkowski (Göttingen)

1919-1931:  Richard Courant (Göttingen), Max Dehn (Frankfurt), Gábor Szegő (Königsberg)

Much of the biographical content can of course be read from home on Wikipedia, but certain facts from the display are unlikely to be encountered elsewhere.   The exhibits, with large photographs and reproductions of handwritten correspondence, offer a sense of communion that it’s difficult to feel over the internet.  I certainly learned some things I didn’t know before.

For instance, even as late as the mid 19th century, baptism was a prerequisite for holding an academic position in Germany.  The eventual admittance of Jews into academic institutions (as students) was as much motivated by questions of social control (eg the regulation of Jewish medical practitioners) as by liberal political motives.

At the end of the Weimar Republic there were 94 full professorships in mathematics in the German states, and of these 28 were occupied by Jews or scholars of Jewish descent.  After 1933, 127 mathematicians, including five women, were driven out of Germany, as a result of the Law for the Restoration of the Professional Civil Service, a Nazi ordinance with an obvious subtext.

Much of the exhibit focuses on the German Mathematical Society (DMV).  This institution was formed largely because of the efforts of Jewish mathematician Georg Cantor in Halle, around 1890.  In the Nazi era, under the leadership of Wilhelm Süss (and others), the organization was used as a political tool for the persecution of mathematicians with Jewish associations. There are issues related to the continuity of the DMV during the war which I do not fully understand.  However, the exhibition says that the society was reestablished in the French occupation zone in 1948 by Erich Kamke, who lost his professorship in 1937 because of a Jewish spouse.  Certain scholars, in particular Max Dehn, refused to rejoin.  After 1948 Süss had a change of heart and began to deliberately approach Jewish emigre mathematicians.

It is said that the first individual to appreciate the scale of the mass dismissals of German mathematicians during the Nazi period was Max Pinl, who published his findings in Jahresbericht der DMV despite considerable opposition during the mid to late 1960’s.

The exhibition features some interesting personal profiles.  There is a board dedicated to the Jewish graduate students of Hilbert and the oral culture of mathematics they helped to initiate at Göttingen. Orality was a distinguishing feature of the department in the first 3rd of the 20th century.

I had been unaware of the particularly tragic circumstances in which Hausdorff was placed by the war.  In 1938, aged 74, facing age related prejudice in addition to religious persecution, Hausdorff was not able to secure a position abroad, despite letters of appeal (several of them displayed) written on his behalf by figures such as Courant, Weyl, and Von Neumann. He spent the duration of the war under Nazi rule.

Emmy Noether, who has a board almost to herself, was displaced.  Additionally she had a brother Fritz (also a mathematician, at Breslau) who emigrated to the Soviet Union during the war, where he was arrested in 1937 in Stalinist persecutions and shot in 1941.

There is a storyboard describing the history of Moses Mendelssohn and his descendants. Two of his granddaughters married mathematicians, and the offspring of one of these unions was Kurt Hensel, discoverer of the Henselian ring.

Hans Hahn, the thesis supervisor of Gödel, describes an abiding interest in philosophy, and says that he was “almost unfaithful to mathematics, so enticed was I by the charms of philosophy.” This is an interesting remark from the advisor of one of the most philosophical of modern mathematicians. Incidentally Gödel was not Jewish, though he did flee the atmosphere of Vienna in 1936 after his friend and colleague Moritz Schlick was shot dead by a pro-Nazi student.

The exhibition, which is traveling around the world (most recently it was in Chicago) is both touching and disturbing.  With free admission in a beautiful neighborhood, a visit makes a profitable use of a summer afternoon.

NPR made me smile again. Stephen Strogatz was a guest for the game show “Ask Me Another.” Click on the link and you can listen to the entire show, or just scroll down and go straight to his segment (By the way, the show tells you how many degrees the Cornell professor is separated from Kevin Bacon!).

Strogatz on the show says there are two types of people when it comes to math: those who say, “I don’t have a math head,” and those “I’m good with math but don’t know why I need to do it.” The response to the latter, the author of “The Joy of X” says, would be this (paraphrased): You watch Michael Jordan play basketball. You listen to music. You don’t need to do those things but you do because they enrich your life. Math is the same (if your degree/job doesn’t require math, that is). Yes, agreed. But teachers wouldn’t force me to watch Michael Jordan at school…

Math Blog readers, what are your responses to this question: What’s the point of doing math?