On computational complexity of Siegel Julia sets
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Abstract. It is known that some polynomial Julia sets are algorithmically impossible to draw with arbitrary magnification. On the other hand, for a large class of examples the problem of drawing a picture has polynomial complexity. In this paper we demonstrate the existence of computable quadratic Julia sets whose computational complexity is arbitrarily high. 1. Foreword Let us informally say that a compact set in the plane is computable if one can program a computer to draw a picture of this set on the screen, with an arbitrary desired magnification. It was recently shown by the second and third authors, that some Julia sets are not computable [BY]. This in itself is quite surprising to dynamicists – Julia sets are among the “most drawn ” objects in contemporary mathematics, and numerous algorithms exist to produce their pictures. In the cases when one has not been able to produce informative pictures (the dynamically pathological cases, like maps with a Cremer or a highly Liouville Siegel point) the feeling had been that this was due to the immense computational resources required by the known algorithms. The next surprise came with the discovery by the authors of this paper in [BBY] that all Cremer quadratics (or more generally, rational maps without rotation domains) have computable Julia sets. The non-computable examples constructed in [BY] were Siegel quadratic polynomials, and one would expect the Cremer case to be at least as bad if not worse computationally. The natural question to ask is then whether in those cases in which we know the Julia set is computable, but no good pictures exist, the computational complexity of such a set is indeed high. Here at least, our original intuition seems to be correct: it is shown in the present paper that there exist computable Siegel quadratic Julia sets with arbitrarily high computational complexity. An irritating possibility still remains that some Cremer Julia sets are computationally easy (and we just do not go about trying to draw them in the right way). This, however, seems unlikely. We note that the examples constructed in this paper are the first known cases of Julia sets which are not poly-time computable. The second author [Brv] and independently Rettinger [Ret] have previously shown that hyperbolic
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.003 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it