Skip to content

STOC 1500

May 23, 2014


What STOC might have been like in old times

YoungCopernicus
src

Mikolaj Kopernik was a student of the professor mathematum Domenico Novara in 1500. They traveled from Bologna to Rome where Novara gave lectures on mathematics. We imagine that Novara might also have been asked to organize a symposium there on the practice of mathematics with mechanical aids, including the classical ruler-and-compass, abaci, astrolabes, and similar devices. Since the words “theory” and “theoretical” with their modern meanings trace only to the late 1500s, we suppose it might have been called the Symposium on Theology of Calculation (STOC).

Today Dick and I consider how STOC 1500 might have been similar to STOC 2014, which starts at the end of next week.

Novara studied under the mathematician and chess player Luca Pacioli, who worked and roomed with Leonardo da Vinci from 1497 until 1499 when both were forced to leave Milan. That was after a regime change evicted their patron. They went to Venice and Florence in 1500, but plausibly came down to Rome. New patrons helped them found a society in honor of Archimedes to give aegis to the conference. Named the Archimedeanus Consociato Machinarum (ACM), the new association organized an exhibition of da Vinci’s machine models and diagrams to attract interest and donors.

Kopernik would go on to be most known in his lifetime for work in mathematical economics. This included founding the quantity theory of money, which remains a pillar of monetary policy today, and discovering a law that was named for Thomas Gresham later in the 16th Century. This law says that introducing “debased” coinage causes full coinage to be hoarded and withdrawn from circulation, and is summarized as “bad money drives out the good.”

Organization

But now, as a student, Kopernik would do much of the leg-work for the conference. He issued a Vocatus ad submissiones in the official Latin language, and also promoted the conference in German, Polish, Italian, and Greek. Papers poured in and strained Novara’s circle of readers, but the Papal Curia—where Kopernik was serving an apprenticeship—arranged for monks to referee them. The PC gave imprimatur to 28% of the submissions, nihil obstat to another batch which could be posters, and sent the rest to the Inquisition.

Meanwhile the University of Turin honored Pacioli himself with the first Turin Award. Pacioli’s lecture headed the program drawn up for the great 3-day event. The Corsini family from Florence underwrote the renting of a building on land they owned along the Tiber south of the Vatican, to be remitted from registration fees. Da Vinci designed the logo for the proceedings cover:

330px-Divina_proportione

Pacioli’s Keynote

Pacioli’s address was titled “Mechanizable Problems,” and began with these stirring words:

Who of us would not be glad to lift the veil behind which the future lies hidden, to cast a glance at the next advances of our science, and at the secrets of its development during future centuries? … What new methods and new facts in the wide and rich field of mathematical thought will the new centuries disclose?

He proceeded to contrast the ancient Greeks, who “fretted about reasoning,” with Archimedes, “whose Lever raised Truth through Calculation.” He derided the kind of person who “would care about the logical foundation of Euclid’s Elements,” while stating “what we need is the mechanization of results not proofs.” He lamented the great irony that artisans and craftsmen were using all manner of machines for building and fashioning materials, but had scarce any aids for calculating what or how much to do with them, “nor even a Method for balancing their Accounts.” He hailed the methods of the Persian mathematician Muhammad Al-Khwarizmi, saying:

With his tools we can erect a New World, gaining riches even more than by discovering one.

He charged the audience to “build a Constructive Mathematics” starting with a science of forms and proportions—not syllogisms and propositions.

375px-Leonardo_polyhedra

Then Pacioli started on the nature of problems. Instead of spending many pages on what a “mathematical problem” should be of itself, he crisply highlighted that the new science should study relationships between problems. He said the great problems of antiquity should be divided into classes, emphasizing especially:

  • {\mathsf{C}\,}, for “Classical”: those problems solvable with compass and straight-edge alone.

  • {\mathsf{NC}\,}, for “Neo-Classical,” where the straight-edge is allowed to have two marks on it to determine a unit distance.

He noted that the idea of using marks, called neusis, came from classical times, but Archimedes was the first to define criteria for the class to be uniform, hence the “Neo-.” Archimedes himself showed that the problems of Angle Trisection ({\mathsf{AT}}) and Cube Duplication ({\mathsf{CD}}) belong to {\mathsf{NC}}. Of course, Pacioli said, artisans should be free to employ marks provided they followed Archimedes’ criteria. He then unfurled a banner stating what he called “the over-arching problem of our time”:

Estne \displaystyle \;\mathsf{C = NC} ?

He followed by saying that all the questions of antiquity would be greatly simplified if {\mathsf{AT}} or some other problem in {\mathsf{NC}} could be shown to be complete—meaning every other problem in {\mathsf{NC}} could be solved by compass and straight-edge alone using {\mathsf{AT}} as what he called an “Oracle.” Thanking the University of Turin for his award, he proposed that this process be called reductionem Turiniensis.

Pacioli continued with more open problems, 23 in all. He dwelled on solving cubic equations in one variable, which he asserted “ought to be within the reach of people already born.” For his closing he surprised the audience by pulling out coins and dice and items for juggling and doing tricks, saying mathematics should reach these too. Finally he wheeled out a chess table and a set, and nodded to da Vinci to advance with one of his model machines. Saying chess too was based on Calculational Truth, he posed the building of a “Mechanized Player” as a Grand Challenge for the new ACM. This brought rising applause before the participants filed into the hall to take a break, where they tried a new bitter drink imported from North Africa called kahve. Then came the first paper sessions.

Some Papers

As usual we cannot list every one of the wonderful papers that were presented, only some that catch our special interest. Here are their titles and abstracts:

On Volume Calculations. Archimedes raised the problem of extending the now-called Heron’s Formula from areas of triangles to volumes of tetrahedra. We solve it for spherically inscribed polyhedra, by extending techniques for cyclic quadrilaterals.

Multiplicative Complexity of Roman Numbers. One of the primary difficulties of using Roman numbers is that multiplication is easy only when one of the numbers is small. On Roman abaci the multiplication is performed by repeated addition. Multiplication by X, XX, L, and C is shown to be faster on a decimal abacus, but multiplication by XXX remains competitive on a Roman abacus.

Feasibility of Babylonian Abaci. Babylonian abaci enable efficient solution of the notorious Multiplication by XXX Problem, but their scale requires fault-tolerant construction not yet achieved in laboratories. An alternative ‘adiabatic’ process is proposed by which the device is heated and allowed to cool. Data from myriad trials demonstrate base-LX effects that cannot be replicated in like time on Roman or decimal abaci.

Separating Encoding and Decoding. Modern codes suffer from the problem that encryption and decryption use the same process. If enemy spies obtain an encoding device, messages in the field are compromised. We propose schemes by which the encoding key could even be made public without compromise. Integrity of the scheme depends on a classical problem about decomposing whole numbers into indivisibles.

New Ideas on the Quintic. A new approach to solving fifth-degree monic equations is presented, via an abstraction of Khwarizmi’s al-jabr. Presence of a condition called solubility enables calculating a solution. If all quintics can be transformed to avoid an opposing condition called normality, then they are all solvable.

Canonical Hours and Roots. Worshipful time-keeping is shown to solve equations. Terce by terce gives sext, and sext by sext gives Vespers at which we find unity. Thus terce is that of which the square is not itself, but whose square again attains unity. None is the antipode of terce but has the same property: none by none is sext. This miracle reveals that the Creator has ordained every monic equation to be declined completely, by joining all numbers with divisions of His time.

Depth in Long Division. Khwarizmi’s numerals have yielded great savings in papyrus for addition and subtraction, but less so for multiplication and division. The standard division method taught in the universities makes unbounded use of the depth of the sheet. We give rules for conserving depth to the logarithm of the width, and speculate on the existence of constant-depth methods.

Abacus Hierarchies. Some calculations appear to require the abacus operator to finish one part before the next part can be undertaken from its results, but others can be parceled among teams of abaci working simultaneously. These situations may combine where a team may operate, but all members must finish one stage before the next starts. A theory of the number of stages sufficient to solve problems is developed.

Saving Byzantium. Factors contributing to the fall of the Byzantine Empire forty-seven years ago are analyzed. The defeat is traced to a fault in communications between generals of the Byzantine Army. Methods for avoiding this fault and enabling timely consensus on military strategies are proposed and compared.

Several of the posters portrayed new methods for computing pi. There was also a late-afternoon workshop talk for graduate students:

Zero: Place-Holder or Value? The discovery that zero can be used both as a place-holder and as an actual value has created many new research questions. In this talk we will explore some of these. No previous experience with zero is needed for this talk.

Panel Discussion

Stimulation by Pacioli’s keynote prompted the ACM to institute the tradition of having a panel discussion, this time to round out the last day. The status of {\mathsf{C = NC}?} was of course chosen as the topic. The panelists, chaired by the Pope’s own secretary and art enthusiast Sigismondo de’ Conti, split on “equal” or “unequal,” and some good technical questions were raised. A show of hands found over 80% support for “unequal.”

Discussion however soon shifted to the sensitive topic of how to handle numerous people sending in attempts to square the circle, a problem Pacioli had skipped since it was not even known to be in {\mathsf{NC}}. Half the room voiced that such communications should be ignored as vanitas, but others noted they were “probably approximately correct” and felt that worthwhile research could come from them. Even Pacioli said this was one case where a proof was important. Panelists mused about what could be “going on in the mind of a crank.”

At this moment Kopernik in the back raised his hand and came forward. Addressing the secretary, he spoke humbly:

“Your Grace, I can tell what these people think, because I have some perverse ideas myself. They are about the System of the World.”

Novara caught his breath but sidled next to Kopernik for support. While some cassocked doctors glowered, de’ Conti himself beckoned with the softness of age, saying “why ‘perverse’?”

“You see, Your Grace, my ideas are contradicted not only by authority but also by observation, yet I still have them—and I have taken time to pursue them even during my apprenticeship to your Court.”

“Are you simple?” hissed one of the doctors, but Novara hushed him as Kopernik responded:

“No, monsignor—it is the idea that is simple. Or at least simpler—maybe—than the system of Ptolemy. It comes from a humble premise, that we mortals should not claim for ourselves a privileged position in the heavens when it is God who rules, and the Sun—as the source of our Light and Life—ought to center our part.”

“But it is known that heliocentric circles cannot match the observations!” thundered a doctor from the other side, while a few brave souls whispered, “Ellipses, perhaps ellipses—other conics…” Kopernik himself, however, stilled them:

“There is no reason for a regular off-center motion to be ordained, unlike for the comets which are irregular and clearly fallen entities. Symmetric motion carries the highest perfection, and nothing broken from symmetry will serve. I have thought about circular epicycles for my system too, but then it becomes no better than Ptolemy’s. I say therefore, I am lower than your quadrature claimants, for they are convinced amid the folly of their ignorance, while I persist the same even conscious of my error. Yet I tell you, eppure I persist—with no intent of offense—and I think we must abide and not begrudge when others do the same.”

Novara waggled his hands to say “he’s with me,” and led Kopernik back up the room by the shoulder. They soon gave notice that they were returning to Bologna. Later, however, Kopernik was advised he was welcome to try again once he had taken time to deepen his thoughts and make better observations, and De’ Conti’s later successor Johann Widmannstetter kept this promise.

Open Problems

What else might have been seen at STOC 1500? We hope those attending STOC 2014 enjoy it.

[edits at end: “center our part”, linked Widmannstetter; fixed “eppure” link]

25 Comments leave one →
  1. May 23, 2014 7:56 pm

    Great post. Thanks

  2. Anonymous permalink
    May 24, 2014 7:40 am

    An amazing and extremely interesting post. STOC 1500 seems to have had quite a bias on results related to abaci, showing that it was indeed a precursor of STOC today. How would STOC 2500 be? How would our results be perceived 500 years down the line?

  3. May 24, 2014 7:54 am

    Plenary session on algebraic and computational geometry led by Lorenzo Ghiberti, Filippo Brunelleschi, and Battista Alberti.

    • May 24, 2014 9:14 am

      Indeed! Brunelleschi for early calculus-of-variations was left on the cutting-room floor.

      Incidentally the paper bullets are clickable. Two sources for Copernicus were this page by James Hannam and book by Noson Yanofsky. A good bio on Pacioli is here.

  4. Martin Cohen permalink
    May 24, 2014 9:15 am

    Quite amusing.

    The mention of “logarithm” seems premature, though. Perhaps it should be replaced by the number of digits (or characters if Roman numerals are used).

    • May 24, 2014 11:30 am

      Thanks. Our translator condensed and modernized some phrases. The original paper says something with prosthaphaeresis, which Copernicus himself might have picked up from the conference. Added: Our translator replied that she was influenced by the “logarithm before Napier” link at the bottom of the Pacioli bio referenced in my comment above. 🙂

  5. May 24, 2014 4:14 pm

    The properties of “zero” and its place in arithmetic notation would have been well understood for at least 900-1000 years (at least ~300 years even if you count only Europe and neglect Asia, counting from Fibonacci’s version of Indian, Arabic and Persian works) in 1500 CE.

  6. Serge permalink
    May 26, 2014 9:03 am

    “Multiplicative Complexity of Roman Numbers” for professionals… “Zero: Place-Holder or Value?” for students… are you sure it wasn’t the other way around? 🙂

    • May 26, 2014 10:54 am

      Indeed, I feel the understanding of place notation, and zero’s role in it, reached a plateau only with p-adic numbers around 1900. I kept the “multiplicative complexity” item from Dick’s early draft (which had anno-1200 or earlier years in mind) mainly to set up the next one analogizing a quantum computer to a “Babylonian abacus” :-).

  7. Bill Gasarch permalink
    May 26, 2014 7:56 pm

    Great post.
    Two thoughts: (1) The Jesuit schools early on were against innovation so the notion of doing original research would have been frowned upon (2) In those days math, science, philosophy, theology were not distinguished from each other. So to have the program committee accept it you may have to show how it is consistent with church teachings.

    A great book about the controversies in math back then is Infinitesimal: How a dangerous Mathematical Theory Shaped the modern world by Amir Alexander.

    • rjlipton permalink*
      January 2, 2021 12:55 pm

      Bill:

      Let me thank you for Ken…it was all his.

      Best to you and happy new year

      Dick

  8. May 26, 2014 8:32 pm

    I really wonder what mature scientists these days are paid for

  9. Sam-G permalink
    May 27, 2014 5:05 pm

    One thing I never understood about NP-completeness theory… in particular, Cook’s reduction of an NP “computation” to a SAT “expression”.

    On the one hand (the “source” side), you have the “computation” of a problem instance.

    On the other hand (the “target” side), you have the “expression” of a SAT instance.

    So Cook reduces “computation A” to an “expression B” — NOT computation A to computation B — also, NOT expression A to expression B.

    Now, “computation” and “expression” are different entities, NOT the same…. I never understood this — how “computation” can be reduced to an “expression”.

    If expression A was reduced to expression B, and B can be solved in P-time, then A can be solved in P-time. This is perfectly fine. But Cook didn’t do this.

    So (I think) it would be incorrect to say that “solving SAT in P-time implies that any problem in NP can be solved in P-time”.

    I hope someone can explain this.

    • rjlipton permalink*
      January 2, 2021 1:04 pm

      Dear Sam-G:

      There are tons of great places to read about this. Not sure can help. But here goes.

      Imagine you need to solve problems of the form: Is X a prime number? Thus X=2021 the answer is no—do you see why? And for X=2027 the answer is yes.

      But you cannot do it. But you have a friend that can tell if a number X has a factor less than X/10? Do you see why your problem can be reduced to your friends problem?

      This is what is happening here.

      Best

      Dick

  10. July 1, 2014 4:10 pm

    P = NP, The Collapse of Hierarchies
    https://www.academia.edu/7518078/P_NP_The_Collapse_of_Hierarchies

    • rjlipton permalink*
      January 2, 2021 12:56 pm

      Dear Riveros;

      I had trouble with link?

      Dick

Trackbacks

  1. Assorted links
  2. Honor Thy Fathers Correctly | Gödel's Lost Letter and P=NP
  3. A New Twist on Flexagons? | Gödel's Lost Letter and P=NP
  4. Why Is Discrete Math Hard To Teach? | Gödel's Lost Letter and P=NP
  5. Did Euclid Really Mean ‘Random’? | Gödel's Lost Letter and P=NP
  6. Absolute Firsts | Gödel's Lost Letter and P=NP
  7. Peter M. Neumann, 1940–2020 | Gödel's Lost Letter and P=NP
  8. Peter M. Neumann has died – Demo
  9. Alan Selman, 1941–2021 | Gödel's Lost Letter and P=NP

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading