Tagged: Mathematics Toggle Comment Threads | Keyboard Shortcuts

  • richardmitnick 2:51 pm on November 10, 2017 Permalink | Reply
    Tags: , Mathematics, , Taco-The Tensor Algebra Compiler   

    From MIT: “Faster big-data analysis” 

    MIT News
    MIT Widget

    MIT News

    October 30, 2017
    Larry Hardesty

    1
    A new MIT computer system speeds computations involving “sparse tensors,” multidimensional data arrays that consist mostly of zeroes. Image: Christine Daniloff, MIT

    System for performing “tensor algebra” offers 100-fold speedups over previous software packages.

    We live in the age of big data, but most of that data is “sparse.” Imagine, for instance, a massive table that mapped all of Amazon’s customers against all of its products, with a “1” for each product a given customer bought and a “0” otherwise. The table would be mostly zeroes.

    With sparse data, analytic algorithms end up doing a lot of addition and multiplication by zero, which is wasted computation. Programmers get around this by writing custom code to avoid zero entries, but that code is complex, and it generally applies only to a narrow range of problems.

    At the Association for Computing Machinery’s Conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH), researchers from MIT, the French Alternative Energies and Atomic Energy Commission, and Adobe Research recently presented a new system that automatically produces code optimized for sparse data.

    That code offers a 100-fold speedup over existing, non-optimized software packages. And its performance is comparable to that of meticulously hand-optimized code for specific sparse-data operations, while requiring far less work on the programmer’s part.

    The system is called Taco, for tensor algebra compiler. In computer-science parlance, a data structure like the Amazon table is called a “matrix,” and a tensor is just a higher-dimensional analogue of a matrix. If that Amazon table also mapped customers and products against the customers’ product ratings on the Amazon site and the words used in their product reviews, the result would be a four-dimensional tensor.

    “Sparse representations have been there for more than 60 years,” says Saman Amarasinghe, an MIT professor of electrical engineering and computer science (EECS) and senior author on the new paper. “But nobody knew how to generate code for them automatically. People figured out a few very specific operations — sparse matrix-vector multiply, sparse matrix-vector multiply plus a vector, sparse matrix-matrix multiply, sparse matrix-matrix-matrix multiply. The biggest contribution we make is the ability to generate code for any tensor-algebra expression when the matrices are sparse.”

    Joining Amarasinghe on the paper are first author Fredrik Kjolstad, an MIT graduate student in EECS; Stephen Chou, also a graduate student in EECS; David Lugato of the French Alternative Energies and Atomic Energy Commission; and Shoaib Kamil of Adobe Research.

    Science paper:
    The Tensor Algebra Compiler

    Custom kernels

    In recent years, the mathematical manipulation of tensors — tensor algebra — has become crucial to not only big-data analysis but machine learning, too. And it’s been a staple of scientific research since Einstein’s time.

    Traditionally, to handle tensor algebra, mathematics software has decomposed tensor operations into their constituent parts. So, for instance, if a computation required two tensors to be multiplied and then added to a third, the software would run its standard tensor multiplication routine on the first two tensors, store the result, and then run its standard tensor addition routine.

    In the age of big data, however, this approach is too time-consuming. For efficient operation on massive data sets, Kjolstad explains, every sequence of tensor operations requires its own “kernel,” or computational template.

    “If you do it in one kernel, you can do it all at once, and you can make it go faster, instead of having to put the output in memory and then read it back in so that you can add it to something else,” Kjolstad says. “You can just do it in the same loop.”

    Computer science researchers have developed kernels for some of the tensor operations most common in machine learning and big-data analytics, such as those enumerated by Amarasinghe. But the number of possible kernels is infinite: The kernel for adding together three tensors, for instance, is different from the kernel for adding together four, and the kernel for adding three three-dimensional tensors is different from the kernel for adding three four-dimensional tensors.

    Many tensor operations involve multiplying an entry from one tensor with one from another. If either entry is zero, so is their product, and programs for manipulating large, sparse matrices can waste a huge amount of time adding and multiplying zeroes.

    Hand-optimized code for sparse tensors identifies zero entries and streamlines operations involving them — either carrying forward the nonzero entries in additions or omitting multiplications entirely. This makes tensor manipulations much faster, but it requires the programmer to do a lot more work.

    The code for multiplying two matrices — a simple type of tensor, with only two dimensions, like a table — might, for instance, take 12 lines if the matrix is full (meaning that none of the entries can be omitted). But if the matrix is sparse, the same operation can require 100 lines of code or more, to track omissions and elisions.

    Enter Taco

    Taco adds all that extra code automatically. The programmer simply specifies the size of a tensor, whether it’s full or sparse, and the location of the file from which it should import its values. For any given operation on two tensors, Taco builds a hierarchical map that indicates, first, which paired entries from both tensors are nonzero and, then, which entries from each tensor are paired with zeroes. All pairs of zeroes it simply discards.

    Taco also uses an efficient indexing scheme to store only the nonzero values of sparse tensors. With zero entries included, a publicly released tensor from Amazon, which maps customer ID numbers against purchases and descriptive terms culled from reviews, takes up 107 exabytes of data, or roughly 10 times the estimated storage capacity of all of Google’s servers. But using the Taco compression scheme, it takes up only 13 gigabytes — small enough to fit on a smartphone.

    “Many research groups over the last two decades have attempted to solve the compiler-optimization and code-generation problem for sparse-matrix computations but made little progress,” says Saday Sadayappan, a professor of computer science and engineering at Ohio State University, who was not involved in the research. “The recent developments from Fred and Saman represent a fundamental breakthrough on this long-standing open problem.”

    “Their compiler now enables application developers to specify very complex sparse matrix or tensor computations in a very easy and convenient high-level notation, from which the compiler automatically generates very efficient code,” he continues. “For several sparse computations, the generated code from the compiler has been shown to be comparable or better than painstakingly developed manual implementations. This has the potential to be a real game-changer. It is one of the most exciting advances in recent times in the area of compiler optimization.”

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    MIT Seal

    The mission of MIT is to advance knowledge and educate students in science, technology, and other areas of scholarship that will best serve the nation and the world in the twenty-first century. We seek to develop in each member of the MIT community the ability and passion to work wisely, creatively, and effectively for the betterment of humankind.

    MIT Campus

    Advertisements
     
  • richardmitnick 11:24 am on May 28, 2017 Permalink | Reply
    Tags: , , , , , , Mathematics, ,   

    From LLNL: Women in STEM-“Lab engages girls at San Joaquin STEM event” 


    Lawrence Livermore National Laboratory

    Carenda L Martin
    martin59@llnl.gov
    925-424-4715

    The Laboratory participated in an educational outreach event held last month titled, “Engaging Girls in STEM: Making a Connection for Action,” at the San Joaquin County Office of Education facility in Stockton.

    More than 300 young women in grades 6-12 attended the program, which is part of a statewide initiative to encourage young girls and women to pursue education and careers in science, technology, engineering and math (STEM) related fields. The event was hosted by the San Joaquin County Office of Education, State Department of Education and the California Commission on the Status of Women and Girls.

    1
    Girls donned 3D googles to take a 360-degree virtual reality tour of the Lab’s National Ignition and Additive Manufacturing facilities.
    No image credit.

    A panel of women working in STEM fields was featured along with an exhibitor fair, showcasing various STEM programs and professions, such as LLNL, Association of Women in Science, CSU Sacramento, San Joaquin Delta College, University of the Pacific, Stockton Astronomical Society and the World of Wonders (WOW) Museum. Occupational therapists, engineers, microbiologists, neuroscientists, physicians and computer scientists also showcased hands-on, industry-based activities.

    The Laboratory was well represented with a booth that featured 360 degree tours of the National Ignition and Additive Manufacturing facilities via 3D goggles, and a booth with giveaways and information about the San Joaquin Expanding Your Horizons conference for girls, which is now in its 25th year and led and organized by a committee of Lab volunteers.

    Also featured was the Laboratory’s popular Fun With Science program, presented by Nick Williams, featuring experiments involving states of matter, chemistry, electricity, air pressure, etc.

    Employee volunteers included Cary Gellner, Carrie Martin, Norma McTyer (retired), Jeene Villanueva along with Joanna Albala, LLNL’s education program manager, who facilitated the Lab’s involvement.

    3
    STEM Lab volunteers included (from left) Joanna Albala, Jeene Villanueva, Cary Gellner, Carrie Martin, Norma McTyer (retired) and Nick Williams.

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition
    LLNL Campus

    Operated by Lawrence Livermore National Security, LLC, for the Department of Energy’s National Nuclear Security
    Administration
    DOE Seal
    NNSA

     
  • richardmitnick 8:43 pm on May 21, 2017 Permalink | Reply
    Tags: , , , , , Mathematics, NanoFab, ,   

    From NIST: “Nanocollaboration Leads to Big Things” 

    NIST

    May 12, 2017 [Nothing like being timely getting into social media.]

    Ben Stein
    benjamin.stein@nist.gov
    (301) 975-2763

    1
    Entrance to NIST’s Advanced Measurement Laboratory in Gaithersburg, Maryland. Credit: Photo Courtesy HDR Architecture, Inc./Steve Hall Copyright Hedrich Blessing

    Roche Sequencing Solutions engineer Juraj Topolancik was looking for a way to decode DNA from cancer patients in a matter of minutes.

    Rajesh Krishnamurthy, a researcher with the startup company 3i Diagnostics, needed help in fabricating a key component of a device that rapidly identifies infection-causing bacteria.

    Ranbir Singh, an engineer with GeneSiC Semiconductor Inc., in Dulles, Virginia, sought to construct and analyze a semiconductor chip that transmits voltages large enough to power electric cars and spacecraft.

    These researchers all credit the NanoFab, located at the Center for Nanoscale Science and Technology (CNST) on the Gaithersburg, Maryland campus of the National Institute of Standards and Technology (NIST). The NanoFab provides cutting-edge nanotechnology capabilities for NIST scientists that is also accessible to outside users, with supplying the state-of-art tools, know-how and dependability to realize their goals.


    Learn more about the CNST NanoFab, where scientists from government, academia and industry can use commercial, state-of-the-art tools at economical rates, and get help from dedicated, full-time technical support staff. Voices: David Baldwin (Great Ball of Light, Inc.), Elisa Williams (Scientific & Biomedical Microsystems), George Coles (Johns Hopkins Applied Physics Laboratory) and William Osborn (NIST).

    When Krishnamurthy, whose company is based in Germantown, Maryland, needed an infrared filter for the bacteria-identifying chip, proximity was but one factor in reaching out to the NanoFab.

    “Even more important was the level of expertise you have here,” he says. “The attention to detail and the trust we have in the staff is so important—we didn’t have to worry if they would do a good job, which gives us tremendous peace of mind,” Krishnamurthy notes.

    The NanoFab also aided his project in another, unexpected way. Krishnamurthy had initially thought that the design for his company’s device would require a costly, highly customized silicon chip. But in reviewing design plans with engineers at the NanoFab, “they came up with a very creative way” to use a more standard, less expensive silicon wafer that would achieve the same goals, he notes.

    “The impact in the short term is that we didn’t have to pay as much [to build and test] the device at the NanoFab, which matters quite a bit because we’re a start-up company,” says Krishnamurthy. “In the long run, this will be a huge factor in [enabling us to mass produce] the device, keeping our costs low because, thanks to the input from the NanoFab, the source material is not a custom material.”

    Singh came to the NanoFab with a different mission. His company is developing a gallium nitride semiconductor device durable enough to transmit hundreds to thousands of volts without deteriorating. He relies on the NanoFab’s metal deposition tools and high-resolution lithography instruments to finish building and assess the properties of the device.

    2
    Semiconductor device, fabricated with the help of the NanoFab, designed to transmit high voltages.
    Credit: GeneSiC Semiconductor Inc.

    “Not only is there a wide diversity of tools, but within each task there are multiple technologies,” Singh adds.

    For instance, he notes, technologies offered at the NanoFab for depositing exquisitely thin and highly uniform layers of metal—which Singh found crucial for making reliable electrical contacts—include both evaporation and sputtering, he says.

    The wide range of metals available for deposition at the NanoFab, uncommon at other nanotech facilities, was another draw.

    “We needed different metals compared to those commonly used on silicon wafers and the NanoFab provided those materials,” notes Singh.

    Topolancik, the Roche Sequencing Solutions engineer, needed high precision etching and deposition tools to fabricate a device that may ultimately improve cancer treatment. His company‘s plan to rapidly sequence DNA from cancer patients could quickly determine if potential anti-cancer drugs and those already in use are producing the genetic mutations necessary to fight cancer.

    “We want to know if the drug is working, and if not, to stop using it and change the treatment,” says Topolancik.

    In the standard method to sequence the double-stranded DNA molecule, a strand is peeled off and resynthesized, base by base, with each base—cytosine, adenine, guanine and thymine—tagged with a different fluorescent label.

    “It’s a very accurate but slow method,” says Topolancik.

    Instead of peeling apart the molecule, Topolancik is devising a method to read DNA directly, a much faster process. Borrowing a technique from the magnetic recording industry, he sandwiches the DNA between two electrodes separated by a gap just nanometers in width.

    3

    Illustration of experiment to directly identify the base pairs of a DNA strand (denoted by A, C, T, G in graph). Tunneling current flows through DNA placed between two closely spaced electrodes. Different bases allow different amounts of current to flow, revealing the components of the DNA molecule.
    Credit: J. Topolancik/Roche Sequencing Solutions

    According to quantum theory, if the gap is small enough, electrons will spontaneously “tunnel” from one electrode to the other. In Topolancik’s setup, the tunneling electrons must pass through the DNA in order to reach the other electrode.

    The strength of the tunneling current identifies the bases of the DNA trapped between the electrodes. It’s an extremely rapid process, but for the technique to work reliably, the electrodes and the gap between them must be fabricated with extraordinarily high precision.

    That’s where the NanoFab comes in. To deposit layers of different metals just nanometers in thickness on a wafer, Topolancik relies on the NanoFab’s ion beam deposition tool. And to etch a pattern in those ultrathin, supersmooth layers without disturbing them—a final step in fabricating the electrodes—requires the NanoFab’s ion etching instrument.

    “These are specialty tools that are not usually accessible in academic facilities, but here [at the NanoFab] you have full, 24/7 access to them,” says Topolancik. “And if a tool goes down, it gets fixed right away,” he adds. “People here care about you, they want you to succeed because that’s the mission of the NanoFab.” As a result, he notes, “I can get done here in two weeks what would take half a year any place else.”


    Take a 360-degree walking tour of the CNST NanoFab in this video!

    See the full article here.

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    NIST Campus, Gaitherberg, MD, USA

    NIST Mission, Vision, Core Competencies, and Core Values

    NIST’s mission

    To promote U.S. innovation and industrial competitiveness by advancing measurement science, standards, and technology in ways that enhance economic security and improve our quality of life.
    NIST’s vision

    NIST will be the world’s leader in creating critical measurement solutions and promoting equitable standards. Our efforts stimulate innovation, foster industrial competitiveness, and improve the quality of life.
    NIST’s core competencies

    Measurement science
    Rigorous traceability
    Development and use of standards

    NIST’s core values

    NIST is an organization with strong values, reflected both in our history and our current work. NIST leadership and staff will uphold these values to ensure a high performing environment that is safe and respectful of all.

    Perseverance: We take the long view, planning the future with scientific knowledge and imagination to ensure continued impact and relevance for our stakeholders.
    Integrity: We are ethical, honest, independent, and provide an objective perspective.
    Inclusivity: We work collaboratively to harness the diversity of people and ideas, both inside and outside of NIST, to attain the best solutions to multidisciplinary challenges.
    Excellence: We apply rigor and critical thinking to achieve world-class results and continuous improvement in everything we do.

     
  • richardmitnick 7:46 am on May 17, 2017 Permalink | Reply
    Tags: Andrea Bertozzi, Mathematics, ,   

    From UCLA: Women in STEM-“UCLA innovator gets creative with applied mathematics” Andrea Bertozzi 

    UCLA bloc

    UCLA

    Andrea Bertozzi puts math to work solving real-world problems

    May 15, 2017
    Nico Correia

    1
    UCLA mathematician Andrea Bertozzi works on a wide range of problems, ranging from the prediction of crime to the deployment of robotic bees. UCLA

    While her grade school classmates were learning the alphabet and how to count to five, Andrea Bertozzi remembers studying negative numbers and modular arithmetic.

    Math often gets a bad rap as an uncreative left brain-oriented activity, but Bertozzi recalls that, as a child, she was fascinated with it because of its creative potential.

    “Teachers have trouble teaching it that way,” said Bertozzi, a professor of mathematics and director of applied mathematics at UCLA, and the inaugural holder of UCLA’s Betsy Wood Knapp Chair for Innovation and Creativity. “They’re not looking at it the right way.”

    As the director of applied mathematics at UCLA and a member of the UCLA Institute for Digital Research and Education’s Executive Committee, Bertozzi and her colleagues conceive of math as a creative medium that can be practically used to solve real-world problems. “Our department is not one that does routine applications,” she said. “We develop new math on the boundary with other fields.”

    One of Bertozzi’s most publicized projects is an ideal illustration of math in action. In a partnership with the Los Angeles Police Department, Bertozzi and UCLA anthropology professor Jeffrey Brantingham head a research team that developed a mathematical model to predicts where and when crime will most likely happen, based on historical crime data in targeted areas so that police officers can preemptively patrol these districts.

    The model they and their team developed based on an algorithm that “learns,” evolves and adapts to new crime data is based on earthquake science. It takes a triggering event such as a property crime or a burglary and treats it similarly to aftershocks following an earthquake that can be tracked by scientists to figure out where and when the next one will occur.

    Another of Bertozzi’s projects, the deployment of robotic bees, is being done in collaboration with Spring Berman, a robotics expert and an assistant professor of mechanical and aerospace engineering at Arizona State University.

    2
    This ground-based robotic bee was developed by undergraduates under Andrea Bertozzi’s direction to test algorithms needed to guide pollinating “bees” to designated plants.

    Since the late 1990s, the population of bees has plunged because of a combination of factors. Earlier this year, the rusty-patched bumblebee landed on the US Fish and Wildlife Service’s list of endangered species. Without bees to pollinate, humanity runs the risk of losing a wide swath of the world’s flora. One solution that scientists are looking into is the development of robotic bees.

    That’s where Bertozzi’s creative mathematical abilities come in.

    Bertozzi and Berman are studying algorithms that would send out a cloud of these robotic pollinators to certain plants. In the applied math lab at UCLA, undergraduates have created earthbound robotic bees to test path-planning algorithms for simple robots without GPS trackers. The group is planning to present the results of testbed simulation “flights” at a conference.

    Bertozzi isn’t exaggerating when she says she is working on a broad research agenda. Her interest in non-linear partial differential equations and applied mathematics has led to projects in everything from image-processing to cooperative robotics and high-dimensional data analysis.

    “It turns out that a lot of my recent projects have social components,” she said. “I have a lot of ideas; we work on those that I can pitch to the funding agencies.” She and her students have used a powerful computer resource at UCLA, the Hoffman2 Cluster, provided by the Institute of Digital Research and Education, to do their complex calculations.

    Although her research goals are all complex, Bertozzi has a concise philosophy on math.

    “You can think of math as a language that describes the real world,” said Bertozzi. “It’s about always reinventing and adding different structures to things.”

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    UC LA Campus

    For nearly 100 years, UCLA has been a pioneer, persevering through impossibility, turning the futile into the attainable.

    We doubt the critics, reject the status quo and see opportunity in dissatisfaction. Our campus, faculty and students are driven by optimism. It is not naïve; it is essential. And it has fueled every accomplishment, allowing us to redefine what’s possible, time after time.

    This can-do perspective has brought us 12 Nobel Prizes, 12 Rhodes Scholarships, more NCAA titles than any university and more Olympic medals than most nations. Our faculty and alumni helped create the Internet and pioneered reverse osmosis. And more than 100 companies have been created based on technology developed at UCLA.

     
  • richardmitnick 8:58 am on March 4, 2017 Permalink | Reply
    Tags: , , Making math more Lego-like, Mathematics   

    From Harvard: “Making math more Lego-like” 

    Harvard University
    Harvard University

    March 2, 2017
    Peter Reuell

    1
    “[A] picture is worth 1,000 symbols,” quips Professor Arthur Jaffe (left). Jaffe and postdoctoral fellow Zhengwei Liu have developed a pictorial mathematical language that can convey pages of algebraic equations in a single 3-D drawing. Rose Lincoln/Harvard Staff Photographer

    Galileo called mathematics the “language with which God wrote the universe.” He described a picture-language, and now that language has a new dimension.

    The Harvard trio of Arthur Jaffe, the Landon T. Clay Professor of Mathematics and Theoretical Science, postdoctoral fellow Zhengwei Liu, and researcher Alex Wozniakowski has developed a 3-D picture-language for mathematics with potential as a tool across a range of topics, from pure math to physics.

    Though not the first pictorial language of mathematics, the new one, called quon, holds promise for being able to transmit not only complex concepts, but also vast amounts of detail in relatively simple images. The language is described in a February 2017 paper published in the Proceedings of the National Academy of Sciences.

    “It’s a big deal,” said Jacob Biamonte of the Quantum Complexity Science Initiative after reading the research. “The paper will set a new foundation for a vast topic.”

    “This paper is the result of work we’ve been doing for the past year and a half, and we regard this as the start of something new and exciting,” Jaffe said. “It seems to be the tip of an iceberg. We invented our language to solve a problem in quantum information, but we have already found that this language led us to the discovery of new mathematical results in other areas of mathematics. We expect that it will also have interesting applications in physics.”

    When it comes to the “language” of mathematics, humans start with the basics — by learning their numbers. As we get older, however, things become more complex.

    “We learn to use algebra, and we use letters to represent variables or other values that might be altered,” Liu said. “Now, when we look at research work, we see fewer numbers and more letters and formulas. One of our aims is to replace ‘symbol proof’ by ‘picture proof.’”

    The new language relies on images to convey the same information that is found in traditional algebraic equations — and in some cases, even more.

    “An image can contain information that is very hard to describe algebraically,” Liu said. “It is very easy to transmit meaning through an image, and easy for people to understand what they see in an image, so we visualize these concepts and instead of words or letters can communicate via pictures.”

    “So this pictorial language for mathematics can give you insights and a way of thinking that you don’t see in the usual, algebraic way of approaching mathematics,” Jaffe said. “For centuries there has been a great deal of interaction between mathematics and physics because people were thinking about the same things, but from different points of view. When we put the two subjects together, we found many new insights, and this new language can take that into another dimension.”

    In their most recent work, the researchers moved their language into a more literal realm, creating 3-D images that, when manipulated, can trigger mathematical insights.

    “Where before we had been working in two dimensions, we now see that it’s valuable to have a language that’s Lego-like, and in three dimensions,” Jaffe said. “By pushing these pictures around, or working with them like an object you can deform, the images can have different mathematical meanings, and in that way we can create equations.”

    Among their pictorial feats, Jaffe said, are the complex equations used to describe quantum teleportation. The researchers have pictures for the Pauli matrices, which are fundamental components of quantum information protocols. This shows that the standard protocols are topological, and also leads to discovery of new protocols.

    “It turns out one picture is worth 1,000 symbols,” Jaffe said.

    “We could describe this algebraically, and it might require an entire page of equations,” Liu added. “But we can do that in one picture, so it can capture a lot of information.”

    Having found a fit with quantum information, the researchers are now exploring how their language might also be useful in a number of other subjects in mathematics and physics.

    “We don’t want to make claims at this point,” Jaffe said, “but we believe and are thinking about quite a few other areas where this picture-language could be important.”

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    Harvard University campus

    Harvard is the oldest institution of higher education in the United States, established in 1636 by vote of the Great and General Court of the Massachusetts Bay Colony. It was named after the College’s first benefactor, the young minister John Harvard of Charlestown, who upon his death in 1638 left his library and half his estate to the institution. A statue of John Harvard stands today in front of University Hall in Harvard Yard, and is perhaps the University’s best known landmark.

    Harvard University has 12 degree-granting Schools in addition to the Radcliffe Institute for Advanced Study. The University has grown from nine students with a single master to an enrollment of more than 20,000 degree candidates including undergraduate, graduate, and professional students. There are more than 360,000 living alumni in the U.S. and over 190 other countries.

     
  • richardmitnick 3:27 pm on December 30, 2016 Permalink | Reply
    Tags: , , cohomology theories, , Mathematics, Motive - recurring theme, Periods of motion, , The fact that the periods that come from physics are “somehow God-given ...", Weight   

    From Quanta: “Strange Numbers Found in Particle Collisions” 

    Quanta Magazine
    Quanta Magazine

    November 15, 2016
    Kevin Hartnett

    1
    Particle collisions are somehow linked to mathematical “motives.” Xiaolin Zeng for Quanta Magazine

    At the Large Hadron Collider in Geneva, physicists shoot protons around a 17-mile track and smash them together at nearly the speed of light.

    CERN/LHC Map
    CERN LHC Grand Tunnel
    CERN LHC particles
    LHC at CERN

    It’s one of the most finely tuned scientific experiments in the world, but when trying to make sense of the quantum debris, physicists begin with a strikingly simple tool called a Feynman diagram that’s not that different from how a child would depict the situation.

    2
    James O’Brien for Quanta Magazine

    Feynman diagrams were devised by Richard Feynman in the 1940s. They feature lines representing elementary particles that converge at a vertex (which represents a collision) and then diverge from there to represent the pieces that emerge from the crash. Those lines either shoot off alone or converge again. The chain of collisions can be as long as a physicist dares to consider.

    To that schematic physicists then add numbers, for the mass, momentum and direction of the particles involved. Then they begin a laborious accounting procedure — integrate these, add that, square this. The final result is a single number, called a Feynman probability, which quantifies the chance that the particle collision will play out as sketched.

    “In some sense Feynman invented this diagram to encode complicated math as a bookkeeping device,” said Sergei Gukov, a theoretical physicist and mathematician at the California Institute of Technology.

    Feynman diagrams have served physics well over the years, but they have limitations. One is strictly procedural. Physicists are pursuing increasingly high-energy particle collisions that require greater precision of measurement — and as the precision goes up, so does the intricacy of the Feynman diagrams that need to be calculated to generate a prediction.

    The second limitation is of a more fundamental nature. Feynman diagrams are based on the assumption that the more potential collisions and sub-collisions physicists account for, the more accurate their numerical predictions will be. This process of calculation, known as perturbative expansion, works very well for particle collisions of electrons, where the weak and electromagnetic forces dominate. It works less well for high-energy collisions, like collisions between protons, where the strong nuclear force prevails. In these cases, accounting for a wider range of collisions — by drawing ever more elaborate Feynman diagrams — can actually lead physicists astray.

    “We know for a fact that at some point it begins to diverge” from real-world physics, said Francis Brown, a mathematician at the University of Oxford. “What’s not known is how to estimate at what point one should stop calculating diagrams.”

    Yet there is reason for optimism. Over the last decade physicists and mathematicians have been exploring a surprising correspondence that has the potential to breathe new life into the venerable Feynman diagram and generate far-reaching insights in both fields. It has to do with the strange fact that the values calculated from Feynman diagrams seem to exactly match some of the most important numbers that crop up in a branch of mathematics known as algebraic geometry. These values are called “periods of motives,” and there’s no obvious reason why the same numbers should appear in both settings. Indeed, it’s as strange as it would be if every time you measured a cup of rice, you observed that the number of grains was prime.

    “There is a connection from nature to algebraic geometry and periods, and with hindsight, it’s not a coincidence,” said Dirk Kreimer, a physicist at Humboldt University in Berlin.

    Now mathematicians and physicists are working together to unravel the coincidence. For mathematicians, physics has called to their attention a special class of numbers that they’d like to understand: Is there a hidden structure to these periods that occur in physics? What special properties might this class of numbers have? For physicists, the reward of that kind of mathematical understanding would be a new degree of foresight when it comes to anticipating how events will play out in the messy quantum world.

    3
    Lucy Reading-Ikkanda for Quanta Magazine

    A Recurring Theme

    Today periods are one of the most abstract subjects of mathematics, but they started out as a more concrete concern. In the early 17th century scientists such as Galileo Galilei were interested in figuring out how to calculate the length of time a pendulum takes to complete a swing. They realized that the calculation boiled down to taking the integral — a kind of infinite sum — of a function that combined information about the pendulum’s length and angle of release. Around the same time, Johannes Kepler used similar calculations to establish the time that a planet takes to travel around the sun. They called these measurements “periods,” and established them as one of the most important measurements that can be made about motion.

    Over the course of the 18th and 19th centuries, mathematicians became interested in studying periods generally — not just as they related to pendulums or planets, but as a class of numbers generated by integrating polynomial functions like x^2 + 2x – 6 and 3x^3 – 4×2 – 2x + 6. For more than a century, luminaries like Carl Friedrich Gauss and Leonhard Euler explored the universe of periods and found that it contained many features that pointed to some underlying order. In a sense, the field of algebraic geometry — which studies the geometric forms of polynomial equations — developed in the 20th century as a means for pursuing that hidden structure.

    This effort advanced rapidly in the 1960s. By that time mathematicians had done what they often do: They translated relatively concrete objects like equations into more abstract ones, which they hoped would allow them to identify relationships that were not initially apparent.

    This process first involved looking at the geometric objects (known as algebraic varieties) defined by the solutions to classes of polynomial functions, rather than looking at the functions themselves. Next, mathematicians tried to understand the basic properties of those geometric objects. To do that they developed what are known as cohomology theories — ways of identifying structural aspects of the geometric objects that were the same regardless of the particular polynomial equation used to generate the objects.

    By the 1960s, cohomology theories had proliferated to the point of distraction — singular cohomology, de Rham cohomology, étale cohomology and so on. Everyone, it seemed, had a different view of the most important features of algebraic varieties.

    It was in this cluttered landscape that the pioneering mathematician Alexander Grothendieck, who died in 2014, realized that all cohomology theories were different versions of the same thing.

    “What Grothendieck observed is that, in the case of an algebraic variety, no matter how you compute these different cohomology theories, you always somehow find the same answer,” Brown said.

    That same answer — the unique thing at the center of all these cohomology theories — was what Grothendieck called a “motive.” “In music it means a recurring theme. For Grothendieck a motive was something which is coming again and again in different forms, but it’s really the same,” said Pierre Cartier, a mathematician at the Institute of Advanced Scientific Studies outside Paris and a former colleague of Grothendieck’s.

    Motives are in a sense the fundamental building blocks of polynomial equations, in the same way that prime factors are the elemental pieces of larger numbers. Motives also have their own data associated with them. Just as you can break matter into elements and specify characteristics of each element — its atomic number and atomic weight and so forth — mathematicians ascribe essential measurements to a motive. The most important of these measurements are the motive’s periods. And if the period of a motive arising in one system of polynomial equations is the same as the period of a motive arising in a different system, you know the motives are the same.

    “Once you know the periods, which are specific numbers, that’s almost the same as knowing the motive itself,” said Minhyong Kim, a mathematician at Oxford.

    One direct way to see how the same period can show up in unexpected contexts is with pi, “the most famous example of getting a period,” Cartier said. Pi shows up in many guises in geometry: in the integral of the function that defines the one-dimensional circle, in the integral of the function that defines the two-dimensional circle, and in the integral of the function that defines the sphere. That this same value would recur in such seemingly different-looking integrals was likely mysterious to ancient thinkers. “The modern explanation is that the sphere and the solid circle have the same motive and therefore have to have essentially the same period,” Brown wrote in an email.

    Feynman’s Arduous Path

    If curious minds long ago wanted to know why values like pi crop up in calculations on the circle and the sphere, today mathematicians and physicists would like to know why those values arise out of a different kind of geometric object: Feynman diagrams.

    Feynman diagrams have a basic geometric aspect to them, formed as they are from line segments, rays and vertices. To see how they’re constructed, and why they’re useful in physics, imagine a simple experimental setup in which an electron and a positron collide to produce a muon and an antimuon. To calculate the probability of that result taking place, a physicist would need to know the mass and momentum of each of the incoming particles and also something about the path the particles followed. In quantum mechanics, the path a particle takes can be thought of as the average of all the possible paths it might take. Computing that path becomes a matter of taking an integral, known as a Feynman path integral, over the set of all paths.

    Every route a particle collision could follow from beginning to end can be represented by a Feynman diagram, and each diagram has its own associated integral. (The diagram and its integral are one and the same.) To calculate the probability of a specific outcome from a specific set of starting conditions, you consider all possible diagrams that could describe what happens, take each integral, and add those integrals together. That number is the diagram’s amplitude. Physicists then square the magnitude of this number to get the probability.

    This procedure is easy to execute for an electron and a positron going in and a muon and an antimuon coming out. But that’s boring physics. The experiments that physicists really care about involve Feynman diagrams with loops. Loops represent situations in which particles emit and then reabsorb additional particles. When an electron collides with a positron, there’s an infinite number of intermediate collisions that can take place before the final muon and antimuon pair emerges. In these intermediate collisions, new particles like photons are created and annihilated before they can be observed. The entering and exiting particles are the same as previously described, but the fact that those unobservable collisions happen can still have subtle effects on the outcome.

    “It’s like Tinkertoys. Once you draw a diagram you can connect more lines according to the rules of the theory,” said Flip Tanedo, a physicist at the University of California, Riverside. “You can connect more sticks, more nodes, to make it more complicated.”

    By considering loops, physicists increase the precision of their experiments. (Adding a loop is like calculating a value to a greater number of significant digits). But each time they add a loop, the number of Feynman diagrams that need to be considered — and the difficulty of the corresponding integrals — goes up dramatically. For example, a one-loop version of a simple system might require just one diagram. A two-loop version of the same system needs seven diagrams. Three loops demand 72 diagrams. Increase it to five loops, and the calculation requires around 12,000 integrals — a computational load that can literally take years to resolve.

    Rather than chugging through so many tedious integrals, physicists would love to gain a sense of the final amplitude just by looking at the structure of a given Feynman diagram — just as mathematicians can associate periods with motives.

    “This procedure is so complex and the integrals are so hard, so what we’d like to do is gain insight about the final answer, the final integral or period, just by staring at the graph,” Brown said.

    5
    Lucy Reading-Ikkanda for Quanta Magazine

    A Surprising Connection

    Periods and amplitudes were presented together for the first time in 1994 by Kreimer and David Broadhurst, a physicist at the Open University in England, with a paper following in 1995. The work led mathematicians to speculate that all amplitudes were periods of mixed Tate motives — a special kind of motive named after John Tate, emeritus professor at Harvard University, in which all the periods are multiple values of one of the most influential constructions in number theory, the Riemann zeta function. In the situation with an electron-positron pair going in and a muon-antimuon pair coming out, the main part of the amplitude comes out as six times the Riemann zeta function evaluated at three.

    If all amplitudes were multiple zeta values, it would give physicists a well-defined class of numbers to work with. But in 2012 Brown and his collaborator Oliver Schnetz proved that’s not the case. While all the amplitudes physicists come across today may be periods of mixed Tate motives, “there are monsters lurking out there that throw a spanner into the works,” Brown said. Those monsters are “certainly periods, but they’re not the nice and simple periods people had hoped for.”

    What physicists and mathematicians do know is that there seems to be a connection between the number of loops in a Feynman diagram and a notion in mathematics called “weight.” Weight is a number related to the dimension of the space being integrated over: A period integral over a one-dimensional space can have a weight of 0, 1 or 2; a period integral over a two-dimensional space can have weight up to 4, and so on. Weight can also be used to sort periods into different types: All periods of weight 0 are conjectured to be algebraic numbers, which can be the solutions to polynomial equations (this has not been proved); the period of a pendulum always has a weight of 1; pi is a period of weight 2; and the weights of values of the Riemann zeta function are always twice the input (so the zeta function evaluated at 3 has a weight of 6).

    This classification of periods by weights carries over to Feynman diagrams, where the number of loops in a diagram is somehow related to the weight of its amplitude. Diagrams with no loops have amplitudes of weight 0; the amplitudes of diagrams with one loop are all periods of mixed Tate motives and have, at most, a weight of 4. For graphs with additional loops, mathematicians suspect the relationship continues, even if they can’t see it yet.

    “We go to higher loops and we see periods of a more general type,” Kreimer said. “There mathematicians get really interested because they don’t understand much about motives that are not mixed Tate motives.”

    Mathematicians and physicists are currently going back and forth trying to establish the scope of the problem and craft solutions. Mathematicians suggest functions (and their integrals) to physicists that can be used to describe Feynman diagrams. Physicists produce configurations of particle collisions that outstrip the functions mathematicians have to offer. “It’s quite amazing to see how fast they’ve assimilated quite technical mathematical ideas,” Brown said. “We’ve run out of classical numbers and functions to give to physicists.”

    Nature’s Groups

    Since the development of calculus in the 17th century, numbers arising in the physical world have informed mathematical progress. Such is the case today. The fact that the periods that come from physics are “somehow God-given and come from physical theories means they have a lot of structure and it’s structure a mathematician wouldn’t necessarily think of or try to invent,” said Brown.

    Adds Kreimer, “It seems so that the periods which nature wants are a smaller set than the periods mathematics can define, but we cannot define very cleanly what this subset really is.”

    Brown is looking to prove that there’s a kind of mathematical group — a Galois group — acting on the set of periods that come from Feynman diagrams. “The answer seems to be yes in every single case that’s ever been computed,” he said, but proof that the relationship holds categorically is still in the distance. “If it were true that there were a group acting on the numbers coming from physics, that means you’re finding a huge class of symmetries,” Brown said. “If that’s true, then the next step is to ask why there’s this big symmetry group and what possible physics meaning could it have.”

    Among other things, it would deepen the already provocative relationship between fundamental geometric constructions from two very different contexts: motives, the objects that mathematicians devised 50 years ago to understand the solutions to polynomial equations, and Feynman diagrams, the schematic representation of how particle collisions play out. Every Feynman diagram has a motive attached to it, but what exactly the structure of a motive is saying about the structure of its related diagram remains anyone’s guess.

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    Formerly known as Simons Science News, Quanta Magazine is an editorially independent online publication launched by the Simons Foundation to enhance public understanding of science. Why Quanta? Albert Einstein called photons “quanta of light.” Our goal is to “illuminate science.” At Quanta Magazine, scientific accuracy is every bit as important as telling a good story. All of our articles are meticulously researched, reported, edited, copy-edited and fact-checked.

     
  • richardmitnick 12:32 pm on September 12, 2016 Permalink | Reply
    Tags: , , , , Mathematics,   

    From CSIRO: Women in STEM – “Indigenous STEM Awards: discovering our stars” Karlie Noon 

    CSIRO bloc

    Commonwealth Scientific and Industrial Research Organisation

    1
    Karlie’s love of mathematics and astronomy has made her a star in her field.

    You could say ‘it was written in the stars’ for Karlie Noon to come and work for us, but like all good stories it can’t be summed up in a simple sentence.

    Karlie is helping us look for an outstanding Indigenous science, technology, engineering or maths professional to inspire the next generation of young innovators.

    She has a tattoo of the solar system – the sun on her left shoulder, all nine planets, stars and an asteroid belt heading down to her wrist. Not only does it symbolise many hours in the tattooist’s chair, for its wearer, it’s a symbol of her journey.

    Karlie is a 26-year-old Kamilaroi woman who was born and raised in Tamworth. She grew up speaking Kamilaroi and Waradjuri and, by her own admissions, spent more time at home playing games than studying in the classroom.

    While schooling wasn’t an important part of her childhood, it was clear that mathematics was. From being taught once a week at home by a local elder to studying pure maths (the why of maths) at the University of Newcastle, her love of mathematics has been a constant.

    “When I was growing up I didn’t really think that English was important, which is funny because a lot of kids can’t see why maths is important,” Karlie said.

    “But for me, maths was always the most interesting and most important thing to study – and I still love it.”

    It was perhaps a gravitational pull of science and maths that made her change her study path from philosophy to astronomy. As the first in her family to attend university the tattoo was a gift to herself – and it was one of the first things esteemed astronomer Dr Duane Hamacher noticed about Karlie.

    You could say the planets aligned when Dr Hamacher and Karlie were in the same place at the same time, and while planets do align occasionally, any astronomer would know that saying is more fanciful than scientific. Dr Hamacher got the sense that Karlie had more than a little interest in astronomy if she was dedicated enough to get such a tattoo.

    2
    Karlie wants to inspire the next generation of young innovators.

    They met through the BHP Billiton Foundation-funded Aboriginal Summer School for Excellence in Technology and Science (ASSETS). Karlie was a cultural mentor at the ASSETS program, an experience she absolutely loved. She landed the role after applying for an Indigenous Cadetship with us, and would not have missed the experience for the world.

    Eight months after ASSETS 2016 came to a close, Karlie is now researching Indigenous Astronomy with Dr Hamacher. The two share an enthusiasm for the cosmological and Karlie has some amazing insights to offer on the Indigenous perspectives of the study.

    We noticed Karlie’s dedication and skills too. She is now working for us to establish the Indigenous STEM Awards program designed to recognise, reward and celebrate Aboriginal and Torres Strait Islander students and scientists. The awards program has seven individual awards divided into three categories rewarding students, teachers, schools, communities and STEM professionals. For Karlie, she hopes the awards can inspire Aboriginal and Torres Strait Islander students across the country.

    “I want to get the word out that Aboriginal and Torres Strait Islander students are natural scientists – and that doesn’t mean we are good at studying nature, it means we are good at investigating,” Karlie said.

    “There is so much we can do and we are so unique in our approach and that is incredibly valuable in science and STEM.”

    “I’m really looking forward to seeing some amazing students, teachers, schools and professionals applying for the awards, and can’t wait to read their stories.”

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    CSIRO campus

    CSIRO, the Commonwealth Scientific and Industrial Research Organisation, is Australia’s national science agency and one of the largest and most diverse research agencies in the world.

     
  • richardmitnick 9:34 am on August 29, 2016 Permalink | Reply
    Tags: , , Mapping signal paths in proteins could reveal new direction for drug development, Mathematics   

    From ICL: “Mapping signal paths in proteins could reveal new direction for drug development” 

    Imperial College London
    Imperial College London

    26 August 2016
    Hayley Dunning

    1
    Using math previously applied to traffic jams and electrical grids, researchers have developed a new method to map signal propagation in proteins. No image credit

    Proteins are molecules found within every cell in the human body that carry out a wide range of functions essential for life. Many proteins have an ‘active site’ to which other molecules bind, enabling them to perform different functions, such as catalysing biochemical reactions or regulating gene expression.

    Active sites are often targeted by drugs designed to combat a host of diseases caused by malfunctioning proteins.

    However, some proteins also have additional sites to which other molecules bind, causing the protein to shift its shape and altering the functionality of the main active site.

    For example, a protein can be ‘activated’ or ‘deactivated’ through this additional binding. This process is known as ‘allostery’, and these additional allosteric sites are often far away from the main active site in the structure of the protein.

    Many proteins are known to have allosteric sites, and these are crucial to biological function. However, the big mystery has been how to predict if and where such allosteric sites exist, and how signals travel across the protein from allosteric sites to the active site.

    Now, researchers at Imperial College London have used sophisticated mathematical methods to accurately trace the allosteric signals through proteins. Their method, published today in Nature Communications, not only allows them to track the signal by identifying the chemical bonds involved, but also predict new allosteric sites.

    New drug targets

    Allosteric sites are a potentially exciting new target for drugs, since they allow greater flexibility than active sites. The structure of active sites may be shared across several proteins, meaning any drugs targeting that particular structure could have side effects, whereas allosteric sites are more specialised and targetting them could minimise unwanted interferences.

    Study co-author, Professor Mauricio Barahona from the Department of Mathematics at Imperial has been working on the underlying mathematical tools, and has already applied them to the study of traffic jams and cascading failures in electrical grids.

    He said: “The concept is the same in all these cases: we look at how a signal travels within the graph structure, whether that’s cars in the road network of a city, electricity in the power grid, or fluctuations in the chemicals bonds in the structure of a protein.

    “When a line is tripped in a power grid, it can have its largest effect on a distant part of the network. The same principle is at play in allostery.”

    Professor Sophia Yaliraki from the Department of Chemistry at Imperial, who has been working on the underlying chemical theory, added: “The purpose of modelling in each case is to figure out how to interfere with the signal – either to enhance it or disrupt it. Disrupting the signal in proteins could inhibit their function, effectively targeting diseases where proteins are malfunctioning.

    “This depends both on the specific atomic-scale structure of the protein, as well as its overall three-dimensional shape.”

    Mapping influencers

    The mathematical models work by mapping influencers – in this case which chemical bonds influence other bonds in response to a propagating signal from the active site. Despite the large amount of information required, the computational method is “incredibly efficient” according to Professor Yaliraki, allowing signal pathways in large complex proteins to be mapped in minutes.

    The researchers have applied the model to many known allosteric sites, and found they were able to accurately predict their existence and position. Now, they are applying the methodology to proteins that are not yet known for allostery in the hope of identifying new targets for drug development.

    The work is a collaboration between researchers in the Departments of Chemistry and Mathematics, enabled by the EPSRC-funded cross-disciplinary Institute for Chemical Biology at Imperial.

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    Imperial College London

    Imperial College London is a science-based university with an international reputation for excellence in teaching and research. Consistently rated amongst the world’s best universities, Imperial is committed to developing the next generation of researchers, scientists and academics through collaboration across disciplines. Located in the heart of London, Imperial is a multidisciplinary space for education, research, translation and commercialisation, harnessing science and innovation to tackle global challenges.

     
  • richardmitnick 11:21 am on June 10, 2016 Permalink | Reply
    Tags: , , , Laura Shou, Mathematics,   

    From Caltech: Women in Science “Shou Receives Fellowship for Graduate Studies in Germany” Laura Shou 

    Caltech Logo
    Caltech

    06/09/2016
    Lori Dajose

    1
    Laura Shou. Credit: Courtesy of L. Shou

    Laura Shou, a senior in mathematics, has received a Graduate Study Scholarship from the German Academic Exchange Service (DAAD) to pursue a master’s degree in Germany. She will spend one year at the Ludwig-Maximilians-Universität München and the Technische Universität München, studying in the theoretical and mathematical physics (TMP) program.

    The DAAD is the German national agency for the support of international academic cooperation. The organization aims to promote international academic relations and cooperation by offering mobility programs for students, faculty, and administrators and others in the higher education realm. The Graduate Study Scholarship supports highly qualified American and Canadian students with an opportunity to conduct independent research or complete a full master’s degree in Germany. Master’s scholarships are granted for 12 months and are eligible for up to a one-year extension in the case of two-year master’s programs. Recipients receive a living stipend, health insurance, educational costs, and travel.

    “As a math major, I was especially interested in the TMP course because of its focus on the interplay between theoretical physics and mathematics,” Shou says. “I would like to use mathematical rigor and analysis to work on problems motivated by physics. The TMP course at the LMU/TUM is one of the few programs focused specifically on mathematical physics. There are many people doing research in mathematical physics there, and the program also regularly offers mathematically rigorous physics classes.”

    At Caltech, Shou has participated in the Summer Undergraduate Research Fellowship (SURF) program three times, conducting research with Professor of Mathematics Yi Ni on knot theory and topology, with former postdoctoral fellow Chris Marx (PhD ’12) on mathematical physics, and with Professor of Mathematics Nets Katz on analysis. She was the president of the Dance Dance Revolution Club and a member of the Caltech NERF Club and the Caltech Math Club.

    Following her year in Germany, Shou will begin the mathematics PhD program at Princeton.

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    Caltech campus

    The California Institute of Technology (commonly referred to as Caltech) is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering. Its 124-acre (50 ha) primary campus is located approximately 11 mi (18 km) northeast of downtown Los Angeles. “The mission of the California Institute of Technology is to expand human knowledge and benefit society through research integrated with education. We investigate the most challenging, fundamental problems in science and technology in a singularly collegial, interdisciplinary atmosphere, while educating outstanding students to become creative members of society.”

     
  • richardmitnick 11:57 am on May 30, 2016 Permalink | Reply
    Tags: , Mathematics, , Two-hundred-terabyte maths proof is largest ever   

    From Nature: “Two-hundred-terabyte maths proof is largest ever” 

    Nature Mag
    Nature

    26 May 2016
    Evelyn Lamb

    U Texas Stampede Supercomputer. Texas Advanced Computer Center
    U Texas Stampede Supercomputer. Texas Advanced Computer Center

    Three computer scientists have announced the largest-ever mathematics proof: a file that comes in at a whopping 200 terabytes1, roughly equivalent to all the digitized text held by the US Library of Congress. The researchers have created a 68-gigabyte compressed version of their solution — which would allow anyone with about 30,000 hours of spare processor time to download, reconstruct and verify it — but a human could never hope to read through it.

    Computer-assisted proofs too large to be directly verifiable by humans have become commonplace, and mathematicians are familiar with computers that solve problems in combinatorics — the study of finite discrete structures — by checking through umpteen individual cases. Still, “200 terabytes is unbelievable”, says Ronald Graham, a mathematician at the University of California, San Diego. The previous record-holder is thought to be a 13-gigabyte proof2, published in 2014.

    The puzzle that required the 200-terabyte proof, called the Boolean Pythagorean triples problem, has eluded mathematicians for decades. In the 1980s, Graham offered a prize of US$100 for anyone who could solve it. (He duly presented the cheque to one of the three computer scientists, Marijn Heule of the University of Texas at Austin, earlier this month.) The problem asks whether it is possible to colour each positive integer either red or blue, so that no trio of integers a, b and c that satisfy Pythagoras’ famous equation a2 + b2 = c2 are all the same colour. For example, for the Pythagorean triple 3, 4 and 5, if 3 and 5 were coloured blue, 4 would have to be red.

    In a paper* posted on the arXiv server on 3 May, Heule, Oliver Kullmann of Swansea University, UK, and Victor Marek of the University of Kentucky in Lexington have now shown that there are many allowable ways to colour the integers up to 7,824 — but when you reach 7,825, it is impossible for every Pythagorean triple to be multicoloured1. There are more than 102,300 ways to colour the integers up to 7,825, but the researchers took advantage of symmetries and several techniques from number theory to reduce the total number of possibilities that the computer had to check to just under 1 trillion. It took the team about 2 days running 800 processors in parallel on the University of Texas’s Stampede supercomputer to zip through all the possibilities. The researchers then verified the proof using another computer program.

    1
    The numbers 1 to 7,824 can be coloured either red or blue so that no trio a, b and c that satisfies a2 +b2 = c2 is all the same colour. The grid of 7,824 squares here shows one such solution, with numbers coloured red or blue (a white square can be either). But for the numbers 1 to 7,825, there is no solution.

    Facts vs theory

    The Pythagorean triples problem is one of many similar questions in Ramsey theory, an area of mathematics that is concerned with finding structures that must appear in sufficiently large sets. For example, the researchers think that if the problem had allowed three colours, rather than two, they would still hit a point where it would be impossible to avoid creating a Pythagorean triple where a, b and c were all the same colour; indeed, they conjecture that this is the case for any finite choice of colours. Any proof for more colours will probably be much larger even than the 200-terabyte 2-colour proof, unless researchers can simplify the case-by-case checking process with a breakthrough in understanding.

    Although the computer solution has cracked the Boolean Pythagorean triples problem, it hasn’t provided an underlying reason why the colouring is impossible, or explored whether the number 7,825 is meaningful, says Kullmann. That echoes a common philosophical objection to the value of computer-assisted proofs: they may be correct, but are they really mathematics? If mathematicians’ work is understood to be a quest to increase human understanding of mathematics, rather than to accumulate an ever-larger collection of facts, a solution that rests on theory seems superior to a computer ticking off possibilities.

    hat did ultimately occur in the case of the 13-gigabyte proof from 2014, which solved a special case of a question called the Erdős discrepancy problem. A year later, mathematician Terence Tao of the University of California, Los Angeles, solved the general problem the old-fashioned way3 — a much more satisfying resolution.

    Nature doi:10.1038/nature.2016.19990

    Science paper:
    Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer

    References

    Heule, M. J. H., Kullmann, O. & Marek, V. W. Preprint at http://arxiv.org/abs/1605.00723 (2016).
    Show context

    Konev, B. & Lisitsa, A. Preprint at http://arxiv.org/abs/1402.2184 (2014).
    Show context

    Tao, T. Preprint at http://arxiv.org/abs/1509.05363 (2015).
    Show context

    For references, see the original article

    See the full article here .

    Please help promote STEM in your local schools.

    STEM Icon

    Stem Education Coalition

    Nature is a weekly international journal publishing the finest peer-reviewed research in all fields of science and technology on the basis of its originality, importance, interdisciplinary interest, timeliness, accessibility, elegance and surprising conclusions. Nature also provides rapid, authoritative, insightful and arresting news and interpretation of topical and coming trends affecting science, scientists and the wider public.

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: