Expresabilidad de un circuito eléctrico con interruptores probabilísticos

Question

He aquí una pregunta puramente teórica de números que he conocido en nuestro departamento de ingeniería eléctrica.

Llamar a un número $q\in \mathbb{N}$ , bueno si uno puede hacer lo siguiente:

Dado un conjunto de interruptores "probabilísticos", cada uno de los cuales está abierto con probabilidad $\frac{a}{q}$ , $a=1,2,\dots,q-1$ (se tienen infinitos de cada tipo), y dos nodos $U,V$ . Entonces, para cada $n,b\in \mathbb{N}$ tal que $b\le q^n-1$ se puede construir un simple circuito paralelo en serie (donde se puede utilizar cada tipo de interruptor más de una vez) conectando $U$ a $V$ donde la probabilidad de $U\to V$ ser abierto es exactamente $\frac{b}{q^n}$ .

La pregunta es ¿qué números son buenos? Creo que la conjetura es que sólo los números que son múltiplos de $2$ o $3$ son buenas. $5$ por ejemplo, no es bueno, ya que no se puede construir un circuito que esté abierto con una probabilidad exacta $\frac{7}{25}$ .

P.D. Un circuito "simple serie-paralelo" es aquel que se puede construir recursivamente mediante la operación de colocar un interruptor en serie con nuestro circuito o colocar un interruptor en paralelo con nuestro circuito. Por ejemplo, el puente de piedra de trigo no es un simple paralelo en serie. También si uno por ejemplo, conecta entre $U,V$ dos interruptores con probabilidades $p_1,p_2$ (de estar abierto) en serie se obtiene una probabilidad de $p_1p_2$ de la sección $UV$ estando abiertos, mientras que si los conectamos en paralelo obtenemos una probabilidad $1-(1-p_1)(1-p_2)$ de que esté abierto.

EDITAR: Reformularé la pregunta en términos matemáticos sencillos, ya que la pregunta original está mal formulada.

Dejemos que $q\in N$ . Un conjunto $S_q\subset \mathbb{Q}$ contiene todos los números de la forma $\frac{a}{q}$ con $a=1,2,\dots q-1$ . También satisface la propiedad $x\in S_q\implies \frac{ax}{q}\in S_q$ y $x+\frac{a-ax}{q}\in S_q$ para cualquier $a=1,2,\dots q-1$ .

Para lo cual $q$ hace $S_q$ contienen todos los números de la forma $\frac{b}{q^n}$ (donde $b < q^n$ )?

Answer 1

Si $p$ es un primo de tamaño 5 o mayor entonces no es bueno. Podemos elegir un primo $q$ tal que $q$ es mayor que $p$ y menos de $2p-1$ . Si $p$ es mayor que 24 podemos encontrar dicho número utilizando un resultado de este trabajo: Jitsuro Nagura (1952). "Sobre el intervalo que contiene al menos un número primo". Proc. Japan Acad. 28: 177-181. El resultado es que para cualquier número mayor que 24 siempre hay un primo entre $n$ y $(1 + 1 / 5)n$ . He encontrado este resultado aquí Para 5 tenemos el valor 7, para 7, 11, para 11, 17, para 13, 17, para 17, 29 y para 23 29. Así, para $n$ igual a 5 o mayor siempre podemos encontrar ese valor. $q/p^{2}$ tiene que ser representado por un circuito paralelo de tamaño dos con dos elementos paralelos de la forma $a/p$ y $b/p$ con $a$ y $b$ menos de $p$ por lo que debe ser de la forma $1-ab/p^{2}$ con $a$ y $b$ menos de $p$ pero $ab$ debe ser inferior a $(p-1)(p-1)$ pero el valor más pequeño que se puede expresar así es $2p-1/p^{2}$ y tenemos una contradicción.

25 es malo. 31/625 no se puede expresar en este sistema. para obtener 31/625 hay que obtenerlo directamente o por un producto con 31/125. Si obtenemos 31/125 debe implicar dos elementos paralelos cuyo producto debe ser 94 y cuyos denominadores son 25 o menos pero 47 divide a 94 y es un primo mayor que 25 por lo que no podemos obtener 31/125. Si obtenemos 31/625 a partir de elementos paralelos debemos tener dos elementos cuyo producto es 594 si ambos tienen denominador 25 el producto máximo es 576, si uno tiene denominador 5 y el otro denominador 125 el producto máximo es 496. Ambos son menores que 594 por lo que no podemos expresar 31/625 de esta manera. Como hemos agotado todas las posibilidades 31/625 no se puede expresar en este sistema y 25 es malo.

2 es bueno. Podemos obtener cualquier número impar en el rango de 1 a $2^{k+1}$ como numerador de una fracción con denominador $2^{k+1}$ de un número impar en el rango de 1 a $2^{k}$ tomándolo en serie con el elemento 1/2 para aquellos números menores que $2^{k}$ o en paralelo para aquellos números mayores que $2^{k}$ . Si 2 es bueno, entonces $2^{m}$ será buena porque cualquier fracción con su denominador una potencia de $2^{m}$ tendrá un denominador de una potencia de 2. Esto se puede ampliar si cualquier primo $p$ es bueno por un argumento similar $p^{k}$ es bueno. Tenemos que tomar la unión de este conjunto con todos los conjuntos construidos anteriormente para atender los casos en que el numerador es divisible por una potencia de 2.

El 3 es bueno. Si tenemos todas las fracciones cuyos numeradores están en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$ entonces podemos construir todas las fracciones cuyos numeradores están en el rango de 1 a $3^{k+1}$ y cuyo denominador es $3^{k+1}$ tomando fracciones cuyos numeradores estén en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$ en serie con $1/3$ y tomando los mismos valores en serie con $2/3$ junto con todas las fracciones cuyos numeradores están en el rango de 1 a $3^{k}$ y cuyo denominador es $3^{k}$ en paralelo con $1/3$ y luego tomar los mismos valores en paralelo con $2/3$ . Los valores en serie con $1/3$ dará el primer tercio de todas las fracciones cuyos numeradores estén en el rango de 1 a $3^{k+1}$ . Los valores en paralelo con $1/3$ dará el último tercio de todas las fracciones cuyos numeradores estén en el rango de 1 a $3^{k+1}$ . Los valores en serie con 2/3 contendrán todos los valores pares del tercio medio de todas las fracciones cuyos numeradores estén en el rango de 1 a $3^{k+1}$ . Los valores paralelos a 2/3 contendrán todos los valores impar del tercio medio de todas las fracciones cuyos numeradores estén en el rango de 1 a $3^{k+1}$ . Tenemos que tomar la unión de este conjunto con todos los conjuntos construidos anteriormente para atender los casos en que el numerador es divisible por una potencia de 3.

Cualquier producto de cualquier potencia de 3 y cualquier potencia de 2 es bueno. Tenemos las fracciones $1/2$ y $2/3$ y $1/2$ en el conjunto inicial de fracciones para cualquier conjunto. A continuación, utilizamos la fracion $1/3$ y $2/3$ para generar el conjunto deseado de fracciones para cualquier potencia de tres deseada cuyo denominador sea la potencia de tres y cuyo numerador sea cualquier número menor que la potencia de tres. Luego tomamos este conjunto en paralelo con $1/2$ y tomar la unión de este conjunto en serie con $1/2$ . Repetimos este proceso y finalmente obtendremos el conjunto de números cuyo numerador es menor que el producto de la potencia deseada de dos y la potencia deseada de tres y cuyo numerador es el producto deseado del producto deseado de dos y el producto deseado de tres. Tenemos que tomar la unión de este conjunto con todos los conjuntos construidos anteriormente para atender a los casos en que el numerador es divisible por una potencia de 2, una potencia de tres o ambas.

Answer 2

Para cualquier primo $p$ mayor que 3 $p^{2}$ es malo. Si hay primo $q$ mayor que $p^{2}$ y menos de $p^{2}+p-1$ entonces afirmo que $q/p^{4}$ no puede ser expresado y por lo tanto p es malo. Porque $q$ es mayor que $p^{2}$ no se puede expresar mediante fracciones con denominador $p^2$ o menos en serie. Al ser menor que 2p^{2}-1 no se puede expresar mediante fracciones con denominador $p^2$ o menos en paralelo. La única alternativa que queda es el producto de una fracción con denominador $p$ y $q/p^{3}$ . Pero eso significa que $q/p^{3}$ debe expresarse en paralelo, pero el producto máximo es $p^3-p^2-p+1$ lo que significa que el valor mínimo que se puede expresar en paralelo es $p^2+p-1$ pero como $q$ es menor que no se puede expresar de esta manera y hemos terminado. El único problema es encontrar tal $q$ .

Estos son algunos valores $q$ para algunos primos $p$ para el 7 53, para el 11 127, para el 13 171, para el 17 293 y para el 19 367. Ya he demostrado que 25 es malo. Así que para todos los primos menores de 23 y mayores de 3 $p^{2}$ es malo.

Ahora bien, como para cualquier primo 23 o mayor necesitamos un hueco primo de 22 o más que empiece antes de $p^{2}$ y continuando al menos 22 espacios más allá para que el cuadrado del primo sea posiblemente bueno. El primer espacio de longitud 22 se produce después de 1129 por lo que cualquier primo cuyo cuadrado sea menor que 1129 es malo lo que significa que para cualquier primo $p$ menos de 37 $p^2$ es malo. Ahora para cualquier primo 37 o mayor necesitamos un espacio primo de 36 o más empezando antes de $p^2$ y continuando 36 espacios más allá para que el cuadrado del primo sea posiblemente bueno. El primer espacio de longitud 36 ocurre en 9551, así que para cualquier primo menor de 90 $p^2$ es malo. Ahora bien, para que cualquier primo mayor que 90 pueda ser bueno, debe haber un hueco primo de 90 o más a partir de $p^2$ y continuando al menos 90 espacios más allá. El primer espacio de 90 o más ocurre en 360653 así que cualquiera para cualquier primo $p$ menos de 600 $p^2$ es malo. Para que cualquier primo de 600 o más sea bueno, debe haber un hueco primo de al menos 600 que empiece en $p^2$ y continuando al menos 600 espacios más allá. El primer espacio primo de tamaño 600 o más está en 1968188556461 por lo que cualquier primo menor de 1.000.000 y mayor de 3 tendrá $p^2$ malo. Si $p$ es mayor que 1.000.000 entonces para $p^2$ para que sea bueno entonces debe haber una brecha principal de 1.000.000 o más empezando antes de $p^2$ . Ahora el máximo espacio primo para números menores que 1693182318746371 es 1132 así que para todos los primos menores que la raíz cuadrada 3e15 o todos los primos menores que 1e7 el cuadrado del primo es malo. El número utilizado aquí vienen del artículo de wikipedia sobre las brechas primos y el material aquí .

Ahora, para extender la prueba de que todos los primos mayores que 3 tienen cuadrados malos más allá de este punto, observamos lo siguiente Si hay un primo $q$ mayor que $p^{2}$ y menos de $2p^{2}-2$ tal que no sea de la forma $p^{2}+mp-m$ entonces el cuadrado del primo es malo. Estamos modificando nuestro argumento original la fracción $q/p^4$ no puede expresarse mediante fracciones con denominadores de $p^2$ en paralelo o en serie como antes la única manera es conseguir $q/p^3$ por fracciones en paralelo. Pero la única manera de hacerlo es tener una fracción de la forma $p-1/p$ y el otro $p^2-m$ para m menos de $p$ . Esto significa que los únicos primos entre $p^2$ y $2p^{2}-21$ son de la forma $p^{2}+mp-m$ con $m$ menos de $p$ lo que significa que sólo existen los primos menores que $p^2$ y $p-1$ más menos que $2p^{2}-21$ . Pero tenemos lo siguiente El número de primos menores que x es mayor que x/ln(x)+2 y menor que $x/ln(x)-4$ para $x$ superior a 55. Este resultado es del artículo de la wikipedia sobre el teorema de los números primos que da esta cita:

^ Barkley Rosser (enero de 1941). "Explicit Bounds for Some Functions of Prime Numbers". American Journal of Mathematics 63 (1): 211-232. doi:10.2307/2371291.

Ahora, para los primos mayores que $e^14$ podemos utilizar la desigualdad citada y el hecho de que el número de primos debe ser $p^{2}+mp-m$ con $m$ menos de $p$ para obtener una contradicción pero ya tenemos que todos los primos menores de 10000000 tienen cuadrados malos lo que significa que cualquier primo con un posible cuadrado bueno debe ser mayor que $e^{14}$ ya que el cuadrado de $e$ es menor que 10 y, por tanto, cualquier primo mayor que 10000000 debe ser mayor que $e^{14}$ y hemos terminado y el cuadrado de cualquier primo mayor que 3 es malo.