[Update September 4th: Here is a draft of the paper. I wrapped it up early because the Bard hallucination led me to look up the literature a bit more carefully and I found an exercise in Bondy Murty which asks to prove that a planar graph has arboricity 3 or less (“three trees suffice!” Having that result already “known” made me finish up early. I actually am glad not to have know about the planar graph result before as I show a stronger result: every 2-sphere can be neatly colored with 4 colors, meaning that its Kempe chains form 3 forests! It is still a nice result but the corollary that all planar graphs have arboricity 3 or less is less spectacular. ]
There are four major stages of intelligence. The first is to know stuff. The second is to be able to use it. The third is to understand it. The final is to improve it. (see this text [PDF]). Both for human intelligence as well as artificial intelligence, the first two stages are quite easy to understand and implement. You do your homework, learn the terms and algorithms. Teachers know that the third part is harder to learn and teach. Understanding consists of making connections, of seeing the limits of concepts, to question given narratives and relate it to other things. The last stage, the innovative part is the hardest. It has a probabilistic aspect. If one looks at the creativity, then this part requires search, it requires luck, it requires time it requires stimulation. The field of Generative AI has made tremendous progress in that respect. The produce probability distributions on probability spaces of texts allowing so a Markov chain to generate new texts. (Here is something I wrote in 2018, with a simple toy example of a tool generating poems using Markov chains). It is a simple principle but computationally expensive, mostly done on GPUs these days. All AI players now spend much more money on computing than they generate. We are in the buy-in phase.
[PS. As an ordinary person, I can not even get the Chat GPT training data onto my computer because I have not the hard drive space.Especially impressive to see was that the training data have all the books in text form (using OCR). The bot builders have gathered everything, like fed 300’000 books (I myself have only 100’000 electronic books and maybe 10000 math books but scale matters). There are files with all airplanes, files with all Dilbert jokes, files with “disinformation” (the best way to get forbidden stuff is to get hold of the filters which get rid of the forbidden stuff …. ) etc etc. Alone the books used to train the AI take TB’s of data and this is only a small part. I myself would not have the workstation power to work on this amount of data, nor the hard drive space even so, I have several 100 TB drive space in total (but most of it is backup. The actual data are maybe 20 TB, where the bulk is material generated for youtube like drone footages or recordings I did, To compare, when I came to the US (my Next computer had 250 Megabytes hard drive and all my stuff including the operating system had fitted perfectly). Data is exploding. And the demand to clean up the data also. ]
The entire world is now hyperventilating about AI. For me this has been a fascinating year. It started even earlier but accelerated. Technology exploded during my life. 50 years ago, I could get my hands on a first calculator for schools. It was able already to compute square roots. It had costed a few hundred bucks but could do arithmetic. 40 years ago I first could navigate computer networks on the Unix machine Bernina at ETHZ. We could navigate the university network BITNET, telnet freely around in other computers like visiting CERN or even telnet into our local printers. About 30 years ago, computer algebra systems became mainstream. I taught as a course assistant in a course “mathematical software” and one of the tasks given to students was to write a program, that would find an algorithm to solve the Rubik cube. Note that this was not the task to solve the Rubik, but to invent a solver for Rubik in the programming language CAYLEY. It is a task in geometric algebra using algorithms of Schreier and others navigating stabilizer groups in finite groups. 30 years ago, the web appeared. The first web browsers like Mosaic were installed on the public Sun Unix workstations at ETH and it was like a revelation to go from text tools like Gopher or telnet to actual user interfaces. In 1994, I taught my own first math course at Caltech (in dynamical systems theory) and already used course websites. It had been a time, when saying “I’m using the web for teaching” sounded still quite impressive. 5 years later everybody would do it. For AI it took months. Using it last year was considered innovative. Today, there is probably nobody who does not use it. The use of computer algebra systems was in 1995 already very hip (partly due to Harvard calculus). When teaching at the university of Arizona, I taught a differential equations class, where every student sat in front of a computer. It was a time, when educators thought that this is the future that learning should happen linked with the computer. In 2003, 20 years ago, when the computer networks were still wide open, we could still ssh into essentially any machine, I got a grant for building a “math chat bot”. We used already existing components which could talk to each other other we built AI units being able to do math from scratch. It was a time, when “chatbots” were still laughed at. About 10 years ago came the MOOCs revolution with massive online learning; or systems which produce automatic homework for students like webwork (we had used webwork also here at Harvard 20 years ago, ran it on our own servers and were naive enough to believe that instructors would contribute their own problems in Perl, now there are entire companies which run the servers and curate the content). 10 years ago was also a 3D printing hype in education and it was cool to show off 3D printed models in class. Since last year, everybody knows, uses and talks about generative AI.
It did not take long and it is already tiring to listen to folks giving advise in this respect. Universities have put guidelines up but nobody really knows what the best response is to machines doing the job or learning, solving problems, writing essays or doing research for them. I myself have the attitude that it is like using a car instead of walking or biking. I chose not to use a car because it damages my health, my happiness and wastes my time (I still drive cars if I need to of course, like when moving or during a vacation trip) I think it is similar than with AI. If you use AI to do homework or research you should disclose it (you can not compete in a 10 K competition with a bike and pretend you are better than the ones who run). I’m also not so sure how things will develop. What will almost certainly happen is that good AI will cost a lot. There will be AI like Chat GPT for the masses which is good but limited and then there will be high IQ units to be sold with corporate prize tags which are not affordable for the general public but are used by governments, agencies, banks or journalists. It is good therefore to stay healthy, practice our own intelligence. Write texts without the help of assistants even so it will have more errors, is less elegant. (I did not use any AI assistance to write this text). And then there will be manipulation and political agendas put into these AI units. All not disclosed. Whoever controls the content controls the narrative, can influence the masses or sell stuff. One of our main challenges will be to be able to think independently, without possibly manipulated or filtered or limited AI guiding and controlling us. Otherwise, we will be reduced to kettle that just is here to procreate. There will always be propaganda. The last couple of years, there was the propaganda slogan “I made my own research” which was used to prevent the population to buy the narrative (now much proven to be wrong) of the official governments. This will accelerate even more. Once the governments will have their hands on the AI units, they not only will see what individuals work and think, they will also be able to guide them. I myself chose not to use computer algebra systems for research because it is opaque (I use the standalone local version which does not communicate with a server). A very important part of science is that it can be reproduced. How do I know whether an algorithm in a computer algebra system has been implemented correctly or not changed while I even work on it? [We had once in military worked on a house built computer algebra system for cryptology. I worked on implementing a factorization algorithm the Morrison Brillhard scheme and during the work, suddenly things started to go hey-wire. It turned out that a developer had changed the integer square root routine. ] I myself use computer algebra systems but then a fixed version, where I know when I run the same code again, it will produce the same result again. While I work on a code, the algorithms used are not changed (I can chose to use tools which are pulled from the server but then I have to double check that things do not change). This is one of the main problems of AI also: it is not reproducible. Therefore, also any plagiarism attempts will be futile. I asked once an AI to write a text like “oliver knill” would write it and it did. How can teachers see whether something has been AI generated if the student just can ask: write me an essay in the style of a 15 year old student who origins from France. This summer we also experimented with feeding the AI wrong information like give encouraging feedback if it was wrong and give thumbs down if it was right. Just to screw with it. Of course, it will learn who manipulates and who is reliable and select learning from the reliable sources. Resistance looks futile. At the moment, I can only hope they stay as stupid as they are
A simple task for an AI
Yesterday, I asked two different AI units “what is arboricity of a graph”. It is an interesting task given that already the Wikipedia article is very deficient and very few textbooks in graph theory really use the term. I asked the two main AI units “Google bard” and “Chat GPT 4” (two runs there). Both got the main definition right. Bard dared to give even some examples (but this was catastrophic). Chat GPT had one answer completely wrong, the other was ok. I was especially taken aback about the hallucination that the arboricity of a planar graph is at most 3, as I I actually am working on proving this with a lot of effort. But what does Bard think “arboricity” is. It claims that arboricity of a complete graph is the number of vertices. That is obviously against the Nash-Williams formula which immediately gives an upper bound |E|/(|V|-1) which is for a complete graph with n vertices n(n-1)/(2n)= (n-1)/2. As for the claim that the arboricity of a cycle graph is 1, what does Bard think? It might think of a tree as a half open graph where the end point is missing. Then it covers the entire graph. That picture would also explain why for a planar graph we would get 3: Cover the interior of a circular graph with one forest, the circle and then the outer part. The claim that the arboricity of a tree is equal to the number of its vertices is hard to swallow. In any way, the entire set up is a hallucination. The concept of arboricity has not matured yet in the literature enough that the machine can navigate it. In any case, the result I’m working on that the arboricity of a 2-sphere is 3 is, as I still believe, a very hard problem. It is not obvious. It is essentially equivalent to the fact that a planar graph has arboricity 3 or less. This is what Bard claimed to be known and obvious. I myself believe that that it is equivalent to the 4 color theorem. I will talk about this in an other video. I for now know that the ability to cover a planar graph nicely with 3 forests is equivalent to the 4 color theorem! Just use the edge coloring to make a vertex coloring. But I need also to work hard to get from a vertex coloring to an edge coloring that consists of forests, the reason being Kempe Loops.
Here is the answer of Bard. Warning! Most of it is completely wrong.
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned.
Equivalently, it is the minimum number of spanning forests needed to cover all the edges of the graph.
A forest is an acyclic graph, which means that it does not contain any cycles. A spanning forest is a forest that contains all the vertices of the original graph.
The arboricity of a graph can be determined using the following algorithm:
Find the maximum degree of any vertex in the graph.
Let k be the ceiling of the maximum degree.
Create k forests, each of which contains at most k edges.
Add edges to the forests one at a time, in any order.
Stop when all the edges of the graph have been added to one of the forests.
The minimum number of forests that are created in this algorithm is the arboricity of the graph.
The arboricity of a planar graph is always at most 3. This is because any planar graph can be embedded in the plane without any edges crossing, and any graph embedded in the plane can be decomposed into at most 3 forests.
Here are some examples of the arboricity of different graphs:
The arboricity of a complete graph is equal to its number of vertices.
The arboricity of a complete bipartite graph is equal to the minimum of the two parts.
The arboricity of a cycle graph is equal to 1.
The arboricity of a tree is equal to its number of vertices.
The arboricity of a graph is a useful measure of its connectivity. A graph with high arboricity is more connected than a graph with low arboricity. The arboricity of a graph can also be used to solve problems such as finding the minimum number of spanning trees in a graph
And here is the first answer of Chat GPT 4 (also this is wrong)
The arboricity of a graph is a concept in graph theory that gives an indication of how “treelike” a given graph is.
Specifically, the arboricity a(G) of a graph G is the minimum number of forests (collections of trees) into which the
edges of GG can be partitioned. More formally, the arboricity a(G) of a graph G is the smallest integer a such that the
edges of GG can be partitioned into a disjoint sets, each of which spans a forest.
There’s also a useful relation that connects the arboricity of a graph with its maximum degree d.
For any graph G, the arboricity is bounded as follows: a(G) >= [d(G)/2]
There are algorithms and methods to compute or approximate the arboricity of a graph, and this concept has applications
in various areas, including network design and data structure design.
And here is the second answer of Chat GPT 4 (which is not bad and essentially uses Wikipedia stuff).
The arboricity of a graph G is the minimum number of spanning forests (disjoint collections of trees)
needed to cover all the edges of GG. In other words, it’s the smallest integer a such that you
can partition the edge set of G into a disjoint sets, each of which forms a spanning forest of G.
The concept of arboricity is often useful for partitioning graphs in various applications, such as
network design, VLSI design, and in the study of social networks. The arboricity of a graph is denoted by arb(G).
Mathematically, the arboricity arb(G) of a graph G=(V,E) is defined as:
arb(G)=max |E(S)|/(|S|-1) where E(S) is the set of edges with both endpoints in S, and |S| is the number of vertices in V. Note
that the maximum is taken over all non-empty subsets S of V that contain at least two vertices.
Arboricity is an important graph invariant and has applications in algorithms and network theory.
Computing the arboricity of a graph is, in general, a challenging problem.
However, there are approximation algorithms and heuristics for finding it.
The following illustration (I wanted to see a Bard in a cartoon style) was generated by AI. You can see it because of the three legs. AI likes to make stupid mistakes. I imagine the AIs of the future to be like Troubadix in the good old Asterix and Obelix cartoons. Self-confident, self centered, arrogant, trying to impose its art onto the rest of the world. But in the end, it is just being terribly annoying and often wrong. But it might well be reducing us to the stage of animals. I once voiced in a Heise forum concern that I’m still happy to be able to do research better than an AI but that this might change soon. An other reader thought this is no problem, we still have our family, our kids and find purpose in that. Well that is true but if that is our only purpose, to procreate; what distinguishes us from the other life forms, or even from a plant? We will have some serious choices to do. For now, I’m still happy seeing that the machines are so stupid.
P.S> I might come back to this post in a year. I’m actually predicting that in a year, the machines will solve the talks to define and give examples of arboricity very well. The AI has improved enormously the last couple of monnths. Last fall, Chat GPT 3 would have failed a multi-variable calculus exam. This summer, Chat GPT 4, would have been a good student. Harvard university has just given out guidelines to urge posing problems which machines can not solve well. Good luck with that. Especially the ambiguous problems are the problems which machines do pretty well. We start seeing that in CAPTCHAS which get more and more annoying and which we more and more fail as humans. The machines of course have no problem with adapting to a new type of CAPTCHAS once they are released. My own take to AI is that we can not regulate it, that we can not forbid it, that we have to learn to use it responsibly. If a task is to reach the top of some mountain, we can do that with a helicopter (and lots of money) or we can hike up. Going up with the helicopter does not produce any satisfaction. What’s the purpose of that? But climbing something with as little help as possible is an achievement. Like in mountain climbing, where we can chose to climb without pulling us up on ropes or even climb without ropes. In any case, whatever we do, we have to disclose whether we used AI in the process or not, similarly as we have to disclose whether we use computer algebra systems or not. I myself have in research always included the computer algebra code when used. When I use something like Midjourney, I acknowledge it. This is also important because of copy right issues. I’m not the one who drew the picture below. I had only managed it and given the task to the AI:
The next picture was taken from the web, when searching for Troubadix. It is from a toy Playmobil Trouba
