index.jsx

1import { useMemo } from 'react';2import { ready, ink } from '../../../lib/mrly.js';3import { board, axis, rules, tag } from '../../../lib/chart.js';4import { mount, Page, Group, Pick, Slider, Stats, Stat, Note } from '../../../lib/app.jsx';5import { Sketch } from '../../../lib/draw.jsx';6import { useQuery } from '../../../lib/query.js';78const m = await ready();9const LOW = 6;10const HIGH = 16;11const CELLS = 720;12const LEAST = 48;13const STEPS = 1000;14const FLOOR = 0.7;15const FIRST = { level: 16, x: 14348906, focus: 12766858, zoom: 16, three: 15, four: 12 };1617const clamp = (v, lo, hi) => Math.max(lo, Math.min(hi, Math.round(v)));18const whole = (n) => n.toLocaleString('en');19const down = (v) => (Math.floor(v * 1e6) / 1e6).toFixed(6);20const up = (v) => (Math.ceil(v * 1e6) / 1e6).toFixed(6);21const key = (row) => `${row.three},${row.four}`;22const kind = (row) => (row.clean ? 'clean' : row.copy ? 'gap copy' : 'mixed');2324const attempt = (fn) => {25  try {26    return { value: fn(), error: null };27  } catch (error) {28    return { value: null, error };29  }30};3132function paint(b, fills) {33  const { ctx } = b;34  const n = fills.length;35  const step = b.wide / n;36  const gap = step >= 6 ? 1 : step >= 3 ? 0.5 : 0;37  ctx.fillStyle = ink.deep;38  ctx.fillRect(b.x(0), b.roof, b.wide, b.tall);39  ctx.fillStyle = ink.blue;40  fills.forEach((f, i) => {41    if (!f) return;42    ctx.globalAlpha = f;43    ctx.fillRect(b.x(i / n) + gap / 2, b.roof, Math.max(step - gap, 0.5), b.tall);44  });45  ctx.globalAlpha = 1;46}4748function App() {49  const [pick, set] = useQuery(FIRST);50  const level = clamp(pick.level, LOW, HIGH);51  const top = 3 ** level;52  const x = clamp(pick.x, 1, top);53  const zmax = Math.max(0, Math.floor(Math.log2((x + 1) / LEAST)));54  const zoom = clamp(pick.zoom, 0, zmax);55  const span = Math.max(Math.min(LEAST, x + 1), Math.floor((x + 1) / 2 ** zoom));56  const focus = clamp(pick.focus, 0, x);57  const lo = clamp(focus - Math.floor(span / 2), 0, x + 1 - span);58  const hi = lo + span;5960  const read = useMemo(() => attempt(() => JSON.parse(m.sumset_read(level, x))), [level, x]);61  const envelope = useMemo(() => attempt(() => m.sumset_envelope(level, CELLS)), [level]);62  const census = useMemo(() => attempt(() => JSON.parse(m.sumset_pairs(level))), [level]);63  const pairs = census.value ?? [];64  const chosen = pairs.find((row) => row.three === pick.three && row.four === pick.four);65  const here = read.value;66  const gaps = pairs.filter((row) => row.gap);6768  const choose = (row) => set({ three: row.three, four: row.four, x: row.gap ? row.gap[1] : row.largest, focus: row.largest });69  const logx = (f) => clamp(Math.exp(Math.max(0, Math.min(1, f)) * Math.log(top)), 1, top);7071  const overview = (canvas) => {72    const b = board(canvas, 64, { top: 10, bottom: 10 });73    paint(b, m.sumset_strip(level, 0, x + 1, Math.max(1, Math.min(x + 1, Math.floor(b.wide)))));74    const a = b.x(lo / (x + 1)), c = b.x(hi / (x + 1));75    b.ctx.strokeStyle = ink.yellow;76    b.ctx.lineWidth = 2;77    b.ctx.strokeRect(a - 1, b.roof - 5, Math.max(2, c - a) + 2, b.tall + 10);78  };7980  const closeup = (canvas) => {81    const b = board(canvas, 76, { top: 8, bottom: 24 });82    paint(b, m.sumset_strip(level, lo, hi, Math.max(1, Math.min(span, Math.floor(b.wide)))));83    axis(b, [[0, whole(lo)], [1, whole(hi - 1)]]);84  };8586  const density = (canvas) => {87    const b = board(canvas, 320, { top: 24, bottom: 24 });88    const { ctx } = b;89    const fx = (v) => Math.log(v) / Math.log(top);90    const fy = (v) => (v - FLOOR) / (1 - FLOOR);91    for (const row of gaps) {92      const a = b.x(fx(row.gap[0])), c = b.x(fx(row.gap[1] + 1));93      ctx.fillStyle = row === chosen ? ink.yellow : ink.line;94      ctx.globalAlpha = row === chosen ? 0.35 : 1;95      ctx.fillRect(a, b.roof, Math.max(1.5, c - a), b.tall);96    }97    ctx.globalAlpha = 1;98    ctx.strokeStyle = ink.line;99    ctx.fillStyle = ink.dim;100    ctx.textAlign = 'right';101    for (const v of [0.8, 0.9, 1]) {102      ctx.beginPath();103      ctx.moveTo(b.x(0), b.y(fy(v)));104      ctx.lineTo(b.x(1), b.y(fy(v)));105      ctx.stroke();106      ctx.fillText(v.toFixed(1), b.x(1) - 2, b.y(fy(v)) - 3);107    }108    ctx.textAlign = 'left';109    const band = envelope.value;110    if (band) {111      const w = b.wide / CELLS;112      ctx.fillStyle = ink.blue;113      for (let i = 0; i < CELLS; i++) {114        const low = band[2 * i], high = band[2 * i + 1];115        if (Number.isNaN(low)) continue;116        const y0 = b.y(fy(high)), y1 = b.y(fy(Math.max(low, FLOOR)));117        ctx.fillRect(b.x(i / CELLS), y0, Math.max(1, w + 0.3), Math.max(1.5, y1 - y0));118      }119    }120    rules(b, [fx(x)], { color: ink.pink, width: 1.5 });121    if (here) {122      ctx.fillStyle = ink.pink;123      ctx.beginPath();124      ctx.arc(b.x(fx(x)), b.y(fy(Math.max(here.density, FLOOR))), 4, 0, Math.PI * 2);125      ctx.fill();126    }127    const marks = [];128    for (let k = 4; k < level; k += 4) marks.push([k / level, `3^${k}`]);129    axis(b, [[0, '1'], ...marks, [1, `3^${level}`]]);130    const edge = tag(b, 'D(x), least to greatest over each pixel', ink.blue);131    tag(b, 'gaps', ink.dim, 'left', edge + 14);132  };133134  const energy = (canvas) => {135    const b = board(canvas, 240, { top: 24, bottom: 24 });136    const { ctx } = b;137    const n = pairs.length;138    if (!n) return;139    const ceiling = Math.ceil(Math.max(...pairs.map((row) => row.ratio)) * 4 + 1) / 4;140    const fx = (i) => (i + 0.5) / n;141    const fy = (q) => (q - 1) / (ceiling - 1);142    ctx.strokeStyle = ink.line;143    ctx.fillStyle = ink.dim;144    for (let q = 1; q <= ceiling; q += 0.5) {145      ctx.beginPath();146      ctx.moveTo(b.x(0), b.y(fy(q)));147      ctx.lineTo(b.x(1), b.y(fy(q)));148      ctx.stroke();149      if (q < ceiling) ctx.fillText(q.toFixed(1), b.x(0), b.y(fy(q)) - 3);150    }151    pairs.forEach((row, i) => {152      const px = b.x(fx(i)), py = b.y(fy(row.ratio));153      ctx.beginPath();154      ctx.arc(px, py, row === chosen ? 6 : 4.5, 0, Math.PI * 2);155      if (row.copy) {156        ctx.strokeStyle = ink.dim;157        ctx.lineWidth = 1.5;158        ctx.stroke();159      } else {160        ctx.fillStyle = row.clean ? ink.yellow : ink.blue;161        ctx.fill();162      }163      if (row === chosen) {164        ctx.strokeStyle = ink.fg;165        ctx.lineWidth = 1.5;166        ctx.beginPath();167        ctx.arc(px, py, 9, 0, Math.PI * 2);168        ctx.stroke();169      }170    });171    axis(b, [[fx(0), `k = ${pairs[0].three}`], [fx(n - 1), `k = ${pairs[n - 1].three}`]]);172    const one = tag(b, 'clean', ink.yellow);173    const two = tag(b, 'mixed', ink.blue, 'left', one + 12);174    tag(b, 'gap copy', ink.dim, 'left', two + 12);175  };176177  const controls = (178    <>179      <Group name="Height">180        <Slider label="level" value={level} min={LOW} max={HIGH} show={`3^${level}`} onChange={(v) => set({ level: v, x: Math.min(x, 3 ** v), focus: Math.min(focus, 3 ** v) })} />181      </Group>182      <Group name="Cursor">183        <Slider label="x" value={Math.round((STEPS * Math.log(x)) / Math.log(top))} min={0} max={STEPS} show={whole(x)} onChange={(v) => set({ x: logx(v / STEPS) })} />184        <Pick label="gap" value={chosen?.gap ? key(chosen) : ''} options={[['', 'jump to a gap'], ...gaps.map((row) => [key(row), `(${row.three}, ${row.four}) at ${row.scale.toFixed(3)}`])]}185          onChange={(v) => { const row = gaps.find((r) => key(r) === v); if (row) choose(row); }} />186      </Group>187      <Group name="Zoom">188        <Slider label="zoom" value={zoom} min={0} max={zmax} show={`${whole(span)} integers`} onChange={(v) => set({ zoom: v })} />189      </Group>190    </>191  );192193  return (194    <Page crumb="sumset" title="Three plus four: Erdos problem 125"195      sub={<>Add a number whose base-3 digits are all <code>0</code> or <code>1</code> to one whose base-4 digits are. Just below each near meeting of a power of 3 and a power of 4 the sums <code>S</code> miss a whole run of integers, so the share <code>D(x)</code> of lit integers up to <code>x</code> dips, and along ever closer meetings its lower limit is 0. Whether it returns above one fixed share at arbitrarily large <code>x</code> is open. Jump to a gap, zoom into the strip and watch.</>}196      controls={controls}197      foot={<>The strip is one bit per integer up to <code>3^{level}</code>, built in Rust: the members of <code>A</code> set directly, then each power of 4 folded in by one shift-or pass. Each strip pixel is shaded by the share of lit integers it covers, and the density chart draws the least and the greatest <code>D(x)</code> over each pixel of <code>log x</code>, so every dip shows at its true depth. The energy <code>E(k, m)</code> is summed over the <code>3^m</code> digit strings a difference in <code>B_m</code> can be, each weighted by <code>2</code> to the zero digits it has in base 4 and in balanced ternary. Every count, density, gap and energy comes out of the crates through wasm; the page only draws. The proofs and the census to <code>3^22</code> are on <a href="/research/cobham/">two bases</a>, section Object S.</>}>198      <p className="banner"><span className="chip conjecture">Open</span> Is the upper density of <code>S</code> positive: does <code>D(x)</code> return above one fixed share at arbitrarily large <code>x</code>?</p>199      <p className="sub"><span className="chip proved">Proved</span> No sum lands in the gap <code>(d, min(3^k, 4^m))</code>, <code>d = (3^k - 1)/2 + (4^m - 1)/3</code> the largest sum of <code>A_k + B_m</code>. Where <code>4^m/3^k</code> is near 1 that gap is a sixth of the scale, and iterated along ever closer coincidences it drives the lower density to 0, the answer to the question Erdos asked, checked in Lean on the problem page.</p>200      <div className="panel">201        <h2>S up to x <span>{`${whole(x + 1)} integers from 0, the yellow box the window below`}</span></h2>202        <Sketch draw={overview} deps={[level, x, lo, hi]} onSeek={(f) => set({ focus: clamp(f * x, 0, x) })} role="img" aria-label="The sumset up to x as a strip, each pixel shaded by the share of members" />203        <h2>the window <span>{`${whole(lo)} to ${whole(hi - 1)}, one cell an integer once they fit`}</span></h2>204        <Sketch draw={closeup} deps={[level, lo, hi]} role="img" aria-label="A window of the sumset, lit integers in blue" />205        {here && (206          <Stats>207            <Stat label="x">{whole(x)}</Stat>208            <Stat label="card(S meet [1, x])">{whole(here.count)}</Stat>209            <Stat label="D(x)">{down(here.density)}</Stat>210            <Stat label="x in S">{here.member ? 'yes' : 'no'}</Stat>211          </Stats>212        )}213        <Note error={read.error ?? envelope.error ?? census.error} />214      </div>215      <div className="arena">216        <div className="panel">217          <h2>the density <span>{`D(x) on a log scale from 1 to 3^${level}`}</span></h2>218          <Sketch draw={density} deps={[level, x, envelope.value, chosen]} onSeek={(f) => set({ x: logx(f) })} role="img" aria-label="The density of the sumset against log x, dipping at every shaded gap" />219          <p className="sub">Each grey band is a gap <code>(d, min(3^k, 4^m))</code>, open when <code>4^m/3^k</code> lies between about <code>3/4</code> and <code>3/2</code>. <code>D</code> falls through the band and bottoms out just below <code>min(3^k, 4^m)</code>; what it does after the last band drawn is the open question. Click to move <code>x</code>.</p>220        </div>221        <div className="panel">222          <h2>the energy ratio <span>{`Q(k, m) at ${pairs.length} pairs from k = 6`}</span></h2>223          <Sketch draw={energy} deps={[pairs, chosen]} onSeek={(f) => pairs.length && choose(pairs[clamp(f * pairs.length - 0.5, 0, pairs.length - 1)])} role="img" aria-label="The energy ratio Q at every pair of levels" />224          <p className="sub"><code>Q(k, m) = E(k, m) (d + 1)/4^(k+m)</code> weighs how often two sums of <code>A_k + B_m</code> collide against a flat spread, and Cauchy-Schwarz gives <code>card(A_k + B_m) &gt;= (d + 1)/Q</code>. <span className="chip proved">Proved</span> <code>Q</code> is unbounded, yet for every <code>eps &gt; 0</code> it is below <code>3^(eps k)</code> at every large <code>k</code> and every <code>m</code> with <code>1/3 &lt;= 4^m/3^k &lt; 4</code>, the window every pair here sits in. <span className="chip conjecture">Conjecture</span> <code>Q</code> stays bounded along one infinite chain of pairs, which would put the upper density at least <code>1/Q</code>. Click a dot to pick its pair.</p>225          {chosen && (226            <Stats>227              <Stat label="pair">{`(${chosen.three}, ${chosen.four}), ${kind(chosen)}`}</Stat>228              <Stat label="4^m/3^k">{up(chosen.scale)}</Stat>229              <Stat label="d">{whole(chosen.largest)}</Stat>230              <Stat label="gap">{chosen.gap ? `${whole(chosen.gap[0])} to ${whole(chosen.gap[1])}` : 'none'}</Stat>231              <Stat label="E">{chosen.energy}</Stat>232              <Stat label="Q">{up(chosen.ratio)}</Stat>233              <Stat label="1/Q">{down(chosen.bound)}</Stat>234              <Stat label="fill to d">{down(chosen.fill)}</Stat>235            </Stats>236          )}237        </div>238      </div>239    </Page>240  );241}242243mount(<App />);