text:
## Multiple Bands

There is only a few medium wave stations where I live so I decided to add shortwave as well, to achieve this I used a rotary switch and a 7uH inductor, this is wound on a T50-2 iron oxide toroid, this ensures a high Q factor that would be difficult to achieve with an air core, Unfortunately it’s nearly impossible to tune as it covers near enough the entire shortwave band, so a bit of a failure on my part.

## Antenna Coupling

Originally I used a fixed 10pF coupling capacitor, I have since replaced that with a 35pF variable trimmer capacitor, I find around 25-30pF to be optimal, although it’ll depend upon your antenna and how selective / sensitive you want it.

## Audio Amplifier

To make listening more comfortable and improve reception of weak signals I made an audio amplifier, this can be switched in with a DPDT toggle switch and is powered from four AA batteries, this is capable of driving a 8 ohm loud speaker at a modest volume.

The circuit is nothing special but works quite well, care needs to be taken with the input wiring to avoid hum, shielded or coaxial cable is best.

## Case

This time I decided to make something half decent looking, I glued together some scrap MDF sheet to make a base and front panel, I then applied walnut wood veneer to the front and varnished it, on the front I mounted two 3.5mm jacks, one for crystal earphones and the other the amplifier output, the tuning capacitor, DPDT toggle switch, 1 pole 12 way rotary switch and the volume and gain pots.

On a piece of brass sheet I have a BNC connector for the antenna input, I made a bit of a mess of the veneer during construction but oh well, lesson learned, don’t drill wood veneer.

## Results

Adding an audio amplifier really boosts what can be received, another thing I have considered is adding a LNA (Low Noise Amplifier) as the RF front-end, however at this point it would make more sense to use a different radio technology.

Overall I’m quite pleased with it but there is definitely room for improvement, but for now I’m done with crystal radios, my next attempt will likely be a regenerative or perhaps superheterodyne radio.

A crystal radio is a radio designed for receiving audio (voice) broadcasts, it was invented around the beginning of the 20th century and became extremely popular in the 1920’s and 1930’s, allowing millions of people to access radio broadcasts that otherwise would have been prohibitively expensive, the majority would have been self constructed sets rather than commercial devices, this sparked a huge interest in radio and electronics and ultimately was the catalyst for the rise of commercial radio.

The reduced cost of vacuum tubes and increased reliability led to the downfall of the crystal radio, however it continued to see sporadic usage and has had numerous revivals to the present day, the ease of construction, low cost and no need for a power source means it still sees usage in poor countries and is a popular project for electronics and radio hobbyists.

Crystal radios are primarily designed to receive Amplitude Modulated (AM) broadcasts, although examples have been made that can receive Frequency Modulated (FM) broadcasts, the most common band used is the medium wave broadcast band which roughly spans 530 to 1,700 kHz.

## Theory of Operation

While there are many variations in design all crystal radios consists of four main blocks, the antenna, tuner, detector and speaker.

The antenna is chosen to receive radio waves as efficiently as possible, for medium wave AM band a monopole, loop or ferrite rod antenna is a common choice, there are two options for connecting the antenna to the tuner, magnetic or capacitive coupling, I opted for the latter which is the purpose of C2.

The tuner in the majority of sets consists of a fixed inductor (L1) and a variable tuning capacitor(C1), the tuning capacitor needs a value of at least 500pF to cover the entire medium wave band, for inductance a value between 200uH and 250uH is often used, this forms an LC tank circuit which resonates at a specific frequency, given by the equation:

$$f_0 = \frac {1}{2\pi\sqrt{LC}}$$

Solving for inductance gives the equation:

$$L = \frac {1}{4\pi^2Cf^2}$$

It's preferable to use the lowest inductance possible as longer coils tend to have greater resistance which reduces the Q (quality) factor of the coil, however since Q is tied to bandwidth too much can also be an issue.

In my case for the medium wave band I decided on 220uH inductor and a 720pF tuning capacitor I had in my parts bin, you will most likely want to wind your own inductor as commercial inductors of this value normally use ferrite cores which can introduce losses, it may work fine but I haven’t tested it, in any case using an air core coil is traditional.

The detector (D1 & C3) is used for demodulating (extracting) the audio from the RF carrier, back in the day this was an actual lump of crystal such as galena or iron pyrite, the ‘cat’s whisker’ would be adjusted over the surface until a sensitive spot was found, various alternatives have also been used, for simplicity I went with a 1N34A germanium diode (alternative 1N270), the diode choice is very important, germanium starts to conduct as low as 0.1V, I tried a common silicon 1N4148 which gave very poor sensitivity, a schottky diode may be a viable alternative here, the value of the capacitor is not critical, 1nF worked for me.

Finally for the speaker I used a high impedance piezoelectric earpiece, these have an extremely high impedance, so much so that a 100k resistor (R1) is required to provide a suitable discharge path, traditionally a more conventional high impedance speaker would be used giving an impedance around 3k to 10k, these are still available from places like ebay albeit more expensive.

## Assembly

For designing the inductor I used the excellent free program Coil32 which I highly recommend you check out, this gave me the number of turns required.

Winding the coil is a bit of an art in itself and can only be learned through experience, I typically use a wax coated cardboard tube, wind the coil as neatly as possible, then coat it with more wax to secure it, this has the advantage over varnish that it sets hard right away, in any case the value is not super critical so there is no need to worry if you do not have an LCR meter handy, go with the calculated number of turns and add a few more for luck.

I mounted the coil and tuning capacitor on a piece of scrap wood, since this is so simple I decided against using a PCB and simply wired it point to point, I made provision for swapping the detector parts using female machine pin headers so I could experiment.

I plan on remaking it much nicer at some point, there is many good examples made by Dave Schmarder.

## Testing

Having a strong AM station nearby is pretty much required, you will have trouble receiving weaker stations, although with a good antenna it should be possible, I had no problems receiving a 2kW station located about 3km away even inside the house with a cheap monopole, some European countries no longer broadcast medium wave so you may have more difficulty there.

For a test signal I used my TinySA with 1kHz AM modulation, a signal inserted at -7dBm was clearly audible and was detectable as low as -23dBm, although I noticed a decrease in sensitivity at the low end of the band likely because Q is frequency dependent.

## Improvements

The nice thing about crystal radios is there is a lot of things you can do to improve them, such as adding an audio or RF amplifiers, different bands, different detectors, different coil winding methods, audio transformers and so on, so making one is definitely worth the time.

# Useful Linux Utilities 2020

There are a number of very useful tools that people may not be aware of that can be a significant boost to productivity in your day to day usage of Linux, or just plain cool, this article will cover some of the more interesting ones I have come across, all of these are completely free.

## File

While regular users of the Linux terminal are probably already aware of this tool it’s hard to understate how helpful it can be at times, the file command simply looks at a file and tries to determine what it actually is, this can be very useful if there is no file extension or you suspect a corrupted file, this should be built into your shell so no need to install it.

Using it is very easy, just type file followed by the name of the file you wish to check, it will then display the detected file type.

## qBittorrent

One of my favorite torrent clients, provides all the required features without any additional rubbish, it’s designed similar to uTorrent which was a once very popular torrent client, which is now essentially spyware, qBittorrent is completely open source with active development, it’s also available for multiple operating systems.

One handy feature is an included torrent search engine, however it does tend to produce fake results so I’d still advise manually checking them on a trusted website.

## Flameshot

Flameshot is a very useful tool for taking screenshots, it provides features such as area selection, annotation and image upload (currently imgur only), all the screenshots in this article and probably most on this website are taken with it.

It still has some way to go though before it can match the best Windows tool for screenshots ShareX, still with it being under very active development I’m looking forward to seeing where it goes.

## KeePassXC

It continues to surprises me that there are many people out there still failing to make use of password managers, they’re such a massive boost to security and convenience that I consider them to be essential software.

KeePassXC is a modern fork of KeePass, it’s completely open source and has been trusted by many, including myself for a long time, unlike some password managers it stores your encrypted passwords completely offline, as such it provides a high degree of privacy and security.

## OBS Studio

Open Broadcast Software Studio is a very versatile tool for recording and streaming video, it’s capable of accepting numerous inputs such as your desktop, games, capture cards, webcams and so on and includes a complete audio mixer, even though it’s free and open source this is easily professional level software with extensive capabilities.

OBS is capable of streaming to most (all?) major platforms including YouTube, Twitch and Facebook, it’s very easy to setup and use making it both suitable for beginners and professionals alike, if you need this kind of software I can’t recommend it enough.

## Gufw

Gufw is a graphical front end to the ufw firewall, which itself is a front end to iptables the Linux firewall, setting up a firewall can be a time consuming process if you’re not experienced in doing so, Gufw provides a nice user friendly way to setup and configure a Linux firewall which will help enhance your security with very little effort, it may not be exactly feature packed but it certainly does the job.

If you don’t already have a firewall setup I would strongly recommend trying this.

## Raw Therapee

Raw Therapee is a powerful raw photo processor that is of great value to both professional and amateur photographers, it provides a huge selection of tools for getting the highest quality photos possible from your camera.

It has a very well designed and easy to use interface that puts many commercial tools to shame, combined with being open source and actively developed this is a must have tool for any photographer.

# Steam Deck Update

A few days ago Valve in a somewhat unusual move posted a partial teardown video of the Steam Deck, in particular showing off the battery and M.2 SSD, although the video was filled with various amusing warnings such as “taking out the screws will permanently weaken it”, which as any competent person will know is essentially bullshit, still I can’t blame them for it, as your average user has the intellect of a baked potato and shouldn’t be encouraged.

The overall design and build quality seems very good, in particular the controls appear to be modular which is going to make replacement easy, Valve also suggest they will be providing replacement parts, although this remains to be seen, I have no doubt there will be numerous third party options in any case.

## Updated FAQ

Valve also posted an updated FAQ on the Steam Deck website, some things of particular note are it can be used as a game controller and includes a decent 1.5m USB-C charging cable, the screen is also 10 finger multitouch (although I have no idea why you’d put 10 fingers on it), the rest of it is fairly obvious stuff such as dual boot support, etc.

## Developer Release

Valve have also been shipping early units to a number of game developers, as such there is a decent bit of game footage floating around on Twitter, it has been confirmed by at least one developer that a five hour battery life can be expected from a moderately demanding game, this is a good sign that most players will squeeze at least 4 hours out of it and much more with light games.

## Conclusion

We’re now under three months before the first release units ship, I’m hoping more details are released soon about Steam OS as I have yet to see the anti-cheat improvements promised for EAC and Battleeye, it would also be interesting to try out the new interface which will eventually replace the big picture mode.

If you’ve not already reserved then you’re pretty much out of luck, most if not all regions have slots later than Q2 2022.

# Steam Deck – The Future of Portable Gaming?

Valve Corporation (aka Valve Software), the makers of the popular Steam gaming platform announced the Steam Deck a portable gaming handheld on the 14th July 2021, reservations were opened on the 15th for a small fee, first batches are expected to ship in December 2021, although most people will probably receive theirs in early to mid 2022, reservations are currently only open to select countries and require a previously active Steam account, this is clearly in an effort to deter scalping which has plauged the GPU market.

## Spectifications

The specifications of the Steam Deck have generated a lot of interest, it uses a 64 bit x86-64 CPU made by AMD using the Zen 2 architechture with 4 cores and 8 threads, this is only one generation behind the current Zen 3, this includes the RDNA 2 APU which has been proven to be very capable at running most modern games at or above 60 fps at 1080p.

Combined with 16GB of LPDDR5 RAM it’s expected to out perform nearly all current gaming handhelds, as with many of Valve’s previous products they are likely to be selling this at close to a loss, since the majority of their income comes from the Steam platform rather than the hardware itself.

It features a 7 inch LCD IPS display with touch, which is optically bonded to the front glass, some have questioned why it does not use an OLED display, but given how low they are pushing the price already I would say this is expected, given it’s an IPS panel it will still look great, the display resolution is 1280×800 giving it a 16:10 aspect ratio, this may seem a bit low resolution, but it’s a sensible tradeoff, RDNA 2 may be powerful but resolution is still a big framerate killer, an external monitor can be connected via USB-C DisplayPort if you really want a larger display.

Other features include a 6-axis IMU, bluetooth 5.0, dual band WIFI. stereo microphone and stereo speakers, connectivity includes a 3.5mm headphone/headset jack and a USB-C 3.2 Gen 2 port.

## Battery Life

Valve have stated that it will last between two to eight hours from the internal 40Wh battery, this is more or less what I expected, ultimately how long you get depends on the games you play, very intensive games will naturally drain it faster than a simple game.

For charging and for continuous power it specifies a USB-C 45W PD3.0 power supply, which will likely be included with it, one thing that remains to be seen is if they offer replacement batteries, lithium batteries degrade over time so this could be an important consideration.

## Steam Deck as a PC

Valve are advertising the Steam Deck as a portable PC, in many ways this is true as it is capable of doing anything a PC can do, to facillitate this Valve will be releasing an official dock for it which includes DisplayPort 1.4, HDMI 2.0, Ethernet, one USB 3.1 port and two USB 2.0 ports.

It can be connected to any monitor or TV up to 8k resolution, although if intended for gaming you should not exceed using it on a 1440p monitor as it may struggle to maintain a playable FPS, resolution scaling is an option for higher resolution monitors, although I tend to find this degrades image quality significantly.

It’s hard to say for sure how well it will perform in this scenario, we will need to wait for benchmarks to be sure, but certainly if you don’t have a PC or your PC is very slow this may be a viable solution.

## Input

On the front, the Steam Deck has two analog joysticks with capacitive touch sensing, eight buttons, two trackpads (which Valve note are 55% more responsive than the Steam controller ones); on the top are two bumper buttons and two analog bumper buttons along with the power and volume buttons, on the rear there are four grip buttons, this gives a total of at least 20 assignments which can be adjusted with Steam input.

This should be sufficient for many games, but if you need more then using the USB port or Steam dock with additional controllers is an option.

## Storage

The Steam Deck is available in three tiers, the bottom has 64GB of eMMC storage, the middle has a 256GB NVMe SSD and the top has a 512GB NVMe SSD, it has been revealed that it uses a standard M.2 2230 socket, so upgrading your memory should be possible, Valve seemed reluctant to advertise this as it opens the possibility of buying a low tier version and adding your own SSD, which is cheaper.

Because 64GB is such a small amount of storage I would not recommend it unless you plan on adding your own storage, it might do for some more basic games, but if you want to play large AAA games it will quickly become unworkable with some games exceeding 64GB as it is.

All versions also support additional storage via micro SD card, although this is typically quite slow making it the least desirable option, while we don’t have full specs yet it’s reasonable to assume that eMMC will achieve 300-400MB\s, NVMe 2000MB\s or greater, a good UHC-I SDXC card will give at best around 120MB\s.

Another final option is connecting external storage via the USB 3.2 Gen 2 port, although this kind of defeats the main point of the Steam Deck being portable.

## Pricing

The lowest tier version currently costs £349, the mid tier £459 and the top tier £569, this is extremely good pricing for the hardware you’re getting, the nearest competitor in performance would be the GPD Win Max which is around £584, but it’s not really comparable .

The highest teir is not really that great value for money, so I would suggest going for the mid tier, if you’re willing to install a SSD then the low tier is overall an excellent choice.

## Software

The Steam Deck will be releasing with a new Steam OS 3.0, this time based on Arch Linux, along with the KDE Plasma desktop environment, this is not currently available but I’m hoping they will release this before the Steam Deck starts to ship.

Steam Deck does not place any restrictions on your software, you’re free to essentially do whatever you like, including installing other operating systems, although given hardware support this mostly means Windows or other Linux distributions, although I’m sure people will have fun getting obscure OS’s working on it.

This opens a lot of options besides your Steam library, certainly I expect emulators will become a popular choice allowing you access to many thousands of games, using alternative stores like Epic Games is also an option if you so desire.

The Steam Deck is fully capable of running most Windows only games using Proton, it’s not perfect but it works in most cases, the only real problem at the moment is that Proton will not work with some anti-cheat software, Valve have already confirmed that BattleEye and EAC will have support ready by launch but other anti-cheat software remains uncertain.

## Suitable for Casual Users?

This remains a big question, and generally I would say no, even with the increasing support for Windows games there will be people frustrated at it for not running certain games, or software, at the end of the day it’s still running Linux and some Linux knowledge is preferable to get the most out of it.

Installing Windows is of course an option, but for casual users this may present too much of a problem, it would have been nice to see Valve offer a choice of operating system, maybe they will, it remains to be seen.

## Overall Verdict

Overall while there are still many unanswered questions, what we have seen so far is quite promising, we will likely get more details as we get closer to launch, for now you should reserve it as soon as possible before stock runs out or you end up waiting a long time, reservation is only £4 and you can get it refunded if you change your mind.


text:
A Unified Approach for Network Information Theory

# A Unified Approach for Network Information Theory

Si-Hyeon Lee,  and Sae-Young Chung,  S.-H. Lee is with the Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada (e-mail: sihyeon.lee@utoronto.ca). This work was done when she was at KAIST. S.-Y. Chung is with the Department of Electrical Engineering, KAIST, Daejeon, South Korea (e-mail: sychung@ee.kaist.ac.kr). The material in this paper will be presented in part at IEEE ISIT 2015 [1].
###### Abstract

In this paper, we take a unified approach for network information theory and prove a coding theorem, which can recover most of the achievability results in network information theory that are based on random coding. The final single-letter expression has a very simple form, which was made possible by many novel elements such as a unified framework that represents various network problems in a simple and unified way, a unified coding strategy that consists of a few basic ingredients but can emulate many known coding techniques if needed, and new proof techniques beyond the use of standard covering and packing lemmas. For example, in our framework, sources, channels, states and side information are treated in a unified way and various constraints such as cost and distortion constraints are unified as a single joint-typicality constraint.

Our theorem can be useful in proving many new achievability results easily and in some cases gives simpler rate expressions than those obtained using conventional approaches. Furthermore, our unified coding can strictly outperform existing schemes. For example, we obtain a generalized decode-compress-amplify-and-forward bound as a simple corollary of our main theorem and show it strictly outperforms previously known coding schemes. Using our unified framework, we formally define and characterize three types of network duality based on channel input-output reversal and network flow reversal combined with packing-covering duality.

## I Introduction

In network information theory, we study the fundamental limits of information flow and processing in a network and develop coding strategies that can approach the limits closely. Instead of studying a fully general network, however, we often study simple canonical models such as the multiple-access channel [2], relay channel [3], and distributed source coding [4] because they are easier to study and more importantly because we can get useful insights from studying them. Once such insights are obtained, one can try to develop a more general theory that is applicable to general networks.

However, such a task is challenging and only partial results have been known so far [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], in which network model and/or applied coding technique is limited. For example, network coding [5] and compress-and-forward (CF) [3] were unified as noisy network coding in [8, 9], but does not include decode-and-forward (DF) [3]. DF and partial DF [3] were generalized for single-source multiple-relay single-destination networks [6] and for multicast and broadcast networks [13, 14], respectively. In [10], noisy network coding was combined with network DF [6], but does not allow a relay to perform both partial DF and CF simultaneously. For joint source-channel coding problems, a hybrid analog/digital coding strategy [12] was proposed that recovers and generalizes many previously known results. Such a hybrid coding scheme was applied to some relay networks and was shown to unify both amplify-and-forward (AF) [16] and CF [3]. In [15], a novel framework for proving achievability was proposed based on output statistics of random binning and source–channel duality. One important feature of this framework is that the addition of secrecy is free, i.e., once an achievability result is obtained for a network model using this framework, an achievability result with additional secrecy constraint is immediately obtained. We note that [12] and [15] took a bottom-up approach in a sense that achievability results are separately obtained for each of various network models.

In this paper, we take a top-down approach and prove a unified achievability theorem for a general network scenario with arbitrarily many nodes. Our setup is general enough such that any combination of source coding, channel coding, joint source-channel coding, and coding for computing problems can be treated. Our result recovers most of the exiting achievability results in network information theory as long as they are based on random coding. Some examples of known results recovered by our theorem are listed as follows:

• Channel coding: Gelfand-Pinsker coding [17], Marton’s inner bound for the broadcast channel [18], Han-Kobayashi inner bound for the interference channel [19], [20], coding for channels with action-dependent states [21], interference decoding for a 3-user interference channel [22], [23], Cover-Leung inner bound for the multiple access channel with feedback [24], a combination of partial DF and CF for the relay channel [3], network DF [6], noisy network coding [8, 9], short message noisy network coding with a DF option [10], offset encoding for the multiple access relay channel [25].

• Source coding: Slepian-Wolf coding [4], Wyner-Ziv coding [26], Berger-Tung inner bound for distributed lossy compression [27], [28], Zhang-Berger inner bound for multiple description coding [29].

• Joint source-channel coding: hybrid coding [12] and all previous results recovered by hybrid coding including sending arbitrarily correlated sources over multiple access channels [30], broadcast channels [31], and interference channels [32, 33].

• Coding for computing: coding for computing [34], cascade coding for computing [35].

In Table I, we compare many approaches that attemped to unify various coding strategies.111The check mark ‘✓’ means that the corresponding unification approach subsumes both the model and the achievability bound of previous result.

Our theorem can be useful in proving new achievability results easily and in some cases gives simpler rate expressions than those obtained using conventional approaches. Furthermore, our unified coding can strictly outperform existing schemes. To illustrate this, we show that a generalized decode-compress-amplify-and-forward bound for acyclic networks can be obtained as a simple corollary of our main theorem and show it strictly outperforms previously known coding schemes. As another special case of our main theorem, we derive a generalized decode-compress-and-forward bound for a discrete memoryless network (DMN) in [36], which recovers both noisy network coding [9] and distributed decode-and-forward [13] bounds. This is the first time the partial-decode-compress-and-forward bound (Theorem 7) by Cover and El Gamal [3] is generalized for DMN’s such that each relay performs both partial DF and CF simultaneously.

Our unified coding theorem enables us to state various types of duality arising in network information theory. Specifically, we formally define and characterize three types of network duality based on channel input-output reversal and network flow reversal combined with packing-covering duality. Our duality results include as special cases many known duality relationships in network information theory, e.g., the duality between coding for multiple-access channel [2] and distributed sources [27], [28] (type-I duality), the duality between Gelfand-Pinsker coding [17] and Wyner-Ziv coding [26] (type-II duality), and the duality between coding for multiple-access channel [2] and broadast channel [18] (type-III duality).

Our unified achievability result is enabled by many novel elements such as a unified framework that represents various network problems in a simple and unified way, a unified coding strategy that consists of a few basic ingredients but can emulate known coding techniques if needed, and new proof techniques beyond the use of standard covering and packing lemmas. In our framework, sources, channels, states and side information are treated in a unified way and various constraints such as cost and distortion constraints are combined as a joint-typicality constraint, which is specified by a single joint distribution. Furthermore, we mainly consider acyclic discrete memoryless networks (ADMN) in this paper, where information flows in an acyclic manner. However, we also show our coding theorem can also be applied to general DMN’s by unfolding the network. Graph unfolding was first used in [5] for network coding.

Our coding scheme has four main ingredients, i.e., superposition coding, simultaneous nonunique decoding, simultaneous compression, and symbol-by-symbol mapping. We note that our coding scheme does not explicitly include binning and multicoding, but is still general enough to emulate them if needed. Although each of these coding ingredients is not new, these are tweaked and combined in a special way to enable unification of many previous approaches. In our coding scheme, covering codebooks are used to compress information that each node observes and decodes. These covering codebooks are generated to permit superposition coding [37]. Each node operates according to the following three steps. The first step is simultaneous nonunique decoding [20, 38, 39], where a node uniquely decodes some covering codewords of other nodes together with some other covering codewords that do not need to be decoded uniquely. The next step is simultaneous compression, where the node finds covering codewords simultaneously that carry information about a received channel output sequence and decoded codewords. Since we allow general superposition relationship among covering codebooks, a more general analysis beyond multivariate covering lemma [40, 41] is needed. The last step is a symbol-by-symbol mapping from a received channel output sequence and decoded and covered codewords to a channel input sequence. The technique of using a symbol-by-symbol mapping was introduced in [42], which is referred to as the Shannon strategy. Our symbol-by-symbol mapping from all three, i.e., the channel output sequence and decoded and covered codewords, was first used in [43] for a three-node noncausal relay channel. We note that such a use of symbol-by-symbol mapping results in correlation between a channel input sequence and nonchosen covering codewords and thus the standard packing lemma [41] cannot be applied for the error analysis. Such correlation was problematic in many previous works and solved for some simple networks in [44, 12, 43]. Our proof technique completely solves this correlation issue in a fully general network setup.

This paper is organized as follows. In Section II, we present our unified framework. In Section III, we propose a unified coding scheme and present the main theorem of this paper. We also show various examples to illustrate how to utilize our results. In Section IV, we characterize three types of network duality. To demonstrate usefulness of our unified coding theorem, in Section V, we derive a generalized decode-compress-amplify-and-forward bound as a simple corollary of our theorem and show it strictly outperforms previously known coding schemes. In Section VI, we present a unified coding theorem for the Gaussian case. We conclude this paper in Section VII.

The following notations are used throughout the paper.

### I-a Notation

For two integers and , denotes the set . For a set of real numbers, denotes the -th smallest element in and denotes . For constants and , denotes the vector and denotes where the subscript is omitted when , i.e., . For random variables and , and are defined similarly. For sets and , denotes and denotes where the subscript is omitted when . Consider two real vectors and of length . We say that is smaller than and write if there exists such that for all and . Furthermore, we say that is component-wise smaller than and write if for all . denotes an all-one vector and denotes an identity matrix. When is a Gaussian random vector with mean and covariance matrix , we write . is the indicator function, i.e., it is 1 if and 0 otherwise. denotes a function of that tends to zero as tends to zero.

We follow the notion of typicality in [45], [41]. Let denote the number of occurrences of in the sequence . Then, is said to be -typical (or just typical) for if for every ,

 |πxn(x)/n−p(x)|≤ϵp(x).

The set of all -typical is denoted as , which is shortly denoted as . A jointly typical set (or just a typical set) such as for multiple variables, which will also be denoted as , is naturally defined from the definition of .

## Ii Unified Framework

In this section, we build a unified framework for proving the achievability of many network information theory problems including channel coding, source coding, joint source–channel coding, and coding for computing. Let us first construct a unified framework for point-to-point scenarios and then generalize it to general network scenarios.

### Ii-a Point-to-point scenarios

Consider the standard channel coding and source coding problems [46] illustrated in Fig. 1. These two problems can be stated with the following elements: information to be communicated, node interaction and node processing functions, and the definition of achievability. Let us investigate differences between these two coding problems for each element and discuss how we can unify them into a single framework. In the following, denotes the number of channel uses for channel coding and the number of source symbols for source coding and denotes the rate in each problem.

• Information to be communicated: In channel coding, a message , uniformly distributed over , is communicated from node 1 to node 2. In source coding, a discrete memoryless source (DMS) is given to node 1 and is reconstructed at node 2 (up to a prescribed distortion level in the case of lossy source coding). We can observe that a message can be regarded as a DMS such that . Hence, in both channel coding and source coding problems, we can say that a DMS is given to node 1 and is reconstructed at node 2.

• Node interaction and node processing functions: In channel coding, node 1 communicates with node 2 through a discrete memoryless channel (DMC) , . Node 1 maps to a channel input sequence and node 2 receives a channel output sequence and maps it to . In source coding, node 1 maps to an index and node 2 receives exactly and maps it to . The noiseless communication of an index in source coding can be regarded as a DMC such that . Hence, in both channel coding and source coding problems, we can say that node 1 communicates with node 2 through a DMC , , the processing function at node 1 is a mapping from to , and the processing function at node 2 is a mapping from to . By denoting by and by , we can further unify the notation for sequences and the node processing functions, i.e., a sequence received by node is denoted by , the resultant sequence from processing at node is denoted by , and the node processing function at node is a mapping from to .

• Achievability: In channel coding and lossless source coding problems, a rate is said to be achievable if there exists a sequence of node processing functions such that , where denotes the probability of error event given as . In lossy source coding problem, a rate–distortion pair is said to be achievable if there exists a sequence of node processing functions such that , where is a distortion measure between two arguments.

Now, let us introduce a new definition of achievability from which we can show the achievability of both channel coding and source coding problems in a unified way. We say a joint distribution , shortly denoted as , is achievable if there exists a sequence of node processing functions such that for any , where denotes the probability

 P((Xn1,Xn2,Yn1,Yn2)∉T(n)ϵ)

in which the typical set is defined with respect to . Then, the achievability of appropriately chosen implies the achievability of or in channel coding and source coding problems. For channel coding and lossless source coding problems, is achievable if such that is achievable. For lossy source coding problem, is achievable if such that , is achievable from the typical average lemma [41] and the continuity of the rate-distortion function in .

To see whether the aforementioned unification approach is general enough for point-to-point scenarios, let us consider more general point-to-point scenarios in Fig. 2. First, in channels with noncausal states [17] illustrated in Fig. 2-(a), node 1 observes a message of rate and a state sequence and encodes as . Then, node 2 receives and estimates as . Achievability is defined in the same way as in the channel coding problem. Let us apply the aforementioned unification approach to this problem. Since represents all the information node 1 receives, we let such that and and are independent, where corresponds to the message of rate . But, we cannot use the channel form of to capture the dependency of the channel output on state . This indicates that a more general channel form of is needed in the unified framework. Then, we can let be equal to . If we choose such that , the achievability of implies the achievability of of the original problem.

Next, in lossy source coding with side information [26] represented in Fig. 2-(b), node 1 receives a source sequence and encodes it as an index . Then, node 2 receives the index and side information and reconstructs as up to some distortion level. Achievability is defined in the same way as in the lossy source coding problem. For this problem, we apply the unification approach as follows. We let . Since node 2 has two channel inputs, we let and let the channel be decomposed as , where the channel corresponds to the communication of of rate and hence its capacity is given as , i.e., , and the channel captures the correlation between and the side information . We pick up the target distribution in the same way as in the lossy source coding problem. Furthermore, coding for computing problem [34], where node 2 wishes to reconstruct a function of and up to distortion with respect to a distortion measure , can also be included in this framework by choosing such that , where .

In summary, the achievability of the aforementioned point-to-point coding problems can be shown by considering the following unified framework. Network model is given by as illustrated in Fig. 3 and the objective is specified by a target distribution . is said to be achievable if there exists a sequence of node processing functions, , , such that for any .

### Ii-B General scenarios

In this subsection, we generalize the unified framework in Section II-A to general -node networks. In our unified framework for nodes, we define an -node acyclic discrete memoryless network (ADMN) , , which consists of a set of alphabet pairs , and a collection of conditional pmfs , . Here, and represent any information that comes into and goes out of node , respectively. can be a channel output, message, source, non-causal state information, and any combination of those. can be a channel input, message estimate, reconstructed source, action for generating channel state, and any combination of those. Next, signifies the correlation betweeen information prior to node and information received at node . It can capture channel distribution possibly with states, correlation between distributed sources, and complicated network-wide correlation among sources and channels.

In this network, information flows in one direction and node operations are sequential. Let denote the number of channel uses. First, is generated according to and then node 1 processes based on . Next, is generated according to and then node 2 encodes based on . Similarly, is generated according to and node encodes based on for . Clearly, any layered network [7] or noncausal network (without infinite loop) [47] possibly with noncausal state or side information is represented as an ADMN. Furthermore, any strictly causal (usual discrete memoryless network with relay functions having one sample delay) or causal network (relays without delay [47]) with blockwise operations can be represented as an ADMN by unfolding the network. Note that our unified achievability theorem (Theorem 1) still applies to the unfolded network. Therefore, considering only acyclic DMN (ADMN) in our unified approach is without loss of generality while greatly simplifying our unification approach. In the following subsection, we show several known examples represented by an ADMN.

Achievability is specified using a target joint distribution , which is shortly denoted as . For a set of node processing functions , , the -probability of error is defined as , where the typical set is defined with respect to . We say the target distribution is achievable if there exists a sequence of node processing functions , , such that for any . We note that unifies diverse network demands and constaints. It can be used for designating the source–destination relationship and for imposing distortion and cost constraints.

### Ii-C Examples

In this subsection, we represent some network information theory problems by an ADMN and a target distribution such that the achievability of implies the achievability of the original problem. Let us first consider some examples of single-hop networks.

###### Example 1 (Multiple access channels [2])

For multiple access channel problem with rates and , we choose , , , , , and such that .

###### Example 2 (Distributed lossy compression [27], [28])

For distributed lossy compression problem with rate–distortion pairs and , we let , , , such that and , and such that for , where is a distortion measure between two arguments and .

###### Example 3 (Broadcast channels [18])

For broadcast channel problem with rates and , we choose , , , , , , , and such that , .

###### Example 4 (Multiple description coding [48])

For multiple description coding with rates and distortion triples , and , we choose , , such that , such that , , and such that for , where is a distortion measure between two arguments and .

Next, we show an example of multi-hop networks.

###### Example 5 (Relay channels)

Consider a three-node relay channel , illustrated in Fig. 4-(a), where node 1 wishes to send a message to node 3 with the help of node 2. Let and denote the rate and the number of channel uses, respectively, and let and denote the message of rate at node 1 and the estimated message at node 3, respectively. Then, the node processing function at node 1 is a mapping from to , the node processing function at node 2 at time is a mapping from to , and the node processing function at node 3 is a mapping from to . The probability of error is defined as and a rate is said to be achievable if there exists a sequence of node processing functions such that .

If we assume a blockwise operation at each node, we can represent this network as an ADMN by unfolding the network. Assume transmission blocks, each consisting of channel uses. In the unfolded network illustrated in Fig. 4-(b), we have nodes and the operation of node corresponds to that of node of the original network at the end of block . To reflect the fact that node is originally the same node as node , we assume that node has an orthogonal link of sufficiently large rate to node , which is represented as a dashed line in Fig. 4-(b). Because this unfolded network is acyclic, it can be represented as an ADMN and can be chosen accordingly.

### Ii-D Introduction of a virtual node

The following two propositions are obtained by introducing a virtual node in an ADMN, which turn out to be useful in recovering some known achievability results in Section III.

###### Proposition 1

 (X1,…,XN,Y1,…,YN,N∏k=1p(yk|yk−1,xk−1))

and target distribution . For some and finite set , assume for . Then, we have

 p(y|xv−1,yv−1) =∑yvp(yv|xv−1,yv−1)p(y|xv−1,yv) p(yv|xv−1,yv−1,y) =p(yv|xv−1,yv−1)p(y|xv−1,yv)∑yvp(yv|xv−1,yv−1)p(y|xv−1,yv).

 (X′1,…,X′N+1,Y′1,…,Y′N+1,N+1∏k=1p′(yk|yk−1,xk−1))

and target distribution such that

 X′k=⎧⎨⎩Xk if kv,   Y′k=⎧⎨⎩Yk if kv,
 p′(yk|xk−1,yk−1)=⎧⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪⎩pYk|Xk−1,Yk−1(yk|xk−1,yk−1) if kv+1,

and

 ∑xv,yvp′∗(xN+1,yN+1)=p∗(xv−1,xN+1v+1,yv−1,yN+1v+1).

Then, if is achievable for the -node ADMN, is achievable for the -node ADMN.

{proof}

The proof is straightforward from the observation that the -node ADMN is obtained by introducing a virtual node, whose channel output is and channel input is null, between nodes and in the -node ADMN and reindexing the nodes.

###### Proposition 2

 (X1,…,XN,Y1,…,YN,N∏k=1p(yk|yk−1,xk−1))

such that and for some , , . Let denote the common part of two random variables and , where the common part of two discrete memoryless sources is defined in [49], [50]

 (X′1,…,X′N+1,Y′1,…,Y′N+1,N+1∏k=1p′(yk|yk−1,xk−1))

and target distribution such that

 X′k=⎧⎨⎩Xk if kv1,   Y′k=⎧⎪ ⎪ ⎪⎨⎪ ⎪ ⎪⎩Yk if k
 p′(yk|xk−1,yk−1)=⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩pYk|Xk−1,Yk−1(yk|xk−1,yk−1) if k

and

 ∑xv1,yv1p′∗(xN+1,yN+1)=p∗(xv1−1,xN+1v1+1,yv1−1,yN+1v1+1),

where for or and can be arbitrarily large.

Then, if is achievable for the -node ADMN, is achievable for the -node ADMN.

{proof}

Note that in the -node ADMN, both nodes and observe the common part and hence can share any function of . Thus, we can introduce a virtual node whose channel output is and channel input is and assume that is available at nodes and .

## Iii Unified Coding Theorem

In this section, we propose a unified coding scheme and present the main theorem of this paper, followed by various examples that show how to utilize our results. Our scheme consists of the following ingredients: 1) superposition, 2) simultaneous nonunique decoding, 3) simultaneous compression, and 4) symbol-by-symbol mapping. These are tweaked and combined in a special way to enable unification of many previous approaches. Let us first briefly explain the proposed scheme and introduce related coding parameters. Detailed description of our scheme is given in the proof of Theorem 1.

• Codebook generation: In our coding scheme, covering codebooks are used to compress information that each node observes and decodes. We generate covering codebooks . Let for denote the alphabet for the codeword symbol of . For indexing of codewords, we consider index sets , where for some for each . We denote by the set of indices of ’s associated with in a way that each codeword in is indexed by the vector and hence consists of codewords, i.e., . Each codebook is constructed allowing superposition coding. Let denote the set of the indices of ’s on which is constructed by superposition.

• Node operation: Node operates according to the following three steps as illustrated in Fig. 5.

• Simultaneous nonunique decoding: After receiving , node decodes some covering codewords of previous nodes simultaneously, where some are decoded uniquely and the others are decoded non-uniquely. We denote by and the sets of the indices of ’s whose codewords are decoded uniquely and non-uniquely, respectively, at node .

• Simultaneous compression: After decoding, node finds covering codewords simultaneously according to a conditional pmf that carry some information about the received channel output sequence and uniquely decoded codewords , where denotes the set of the indices of ’s used for compression.

• Symbol-by-symbol mapping: After decoding and compression, node generates by a symbol-by-symbol mapping from uniquely decoded codewords , covered codewords , and received channel output sequence . Let denote the function used for symbol-by-symbol mapping.

In summary, our scheme requires the following set of coding parameters, where some constraints are added to make the aforementioned codebook generation and node operation proper:

1. positive integers and

2. alphabets

3. -rate tuple

4. sets , , , , and for and that satisfy

1. ’s are disjoint,

2. and if ,

3. , , and .

5. a set of conditional pmfs and functions for such that induced by

 N∏k=1p(yk|yk−1,xk−1)p(uWk|uDk,yk)\mathbbm1xk=xk(uDk,uWk,yk) (1)

is the same as the target distribution .

Now, we are ready to present our main theorem, which gives a sufficient condition for achievability using the aforementioned scheme. For an ADMN and target distribution , let , shortly denoted as or , denote the set of all possible ’s.

###### Theorem 1

For an -node ADMN, is achievable if there exists such that for

 ∑j∈¯Skrj <∑j∈SkI(Uj;USk[j]∪Sck,Yk|UAj) (2) ∑j∈¯Tkrj >∑j∈TkI(Uj;UTk[j]∪Dk,Yk|UAj) (3)

for all such that and for all such that , where , , ,

 Sk ≜{j:j∈Dk∪Bk,Γj∩¯Sk≠∅}, (4) Tk ≜{j:j∈Wk,Γj∩(¯Tk∪¯Dk)c=∅}. (5)
###### Remark 1

For , the inequalities (2) and (3) are the conditions for successful simultaneous nonunique decoding and simultaneous compression, respectively, at node .

###### Remark 2

Theorem 1 can be improved using coded time sharing [19].

{proof}

Consider . Let for all such that and . Let

format: plain


text:
OpenStudy (anonymous):

A ball rolls off a horizontal table 1 m high with a velocity of 3 m/s. Find: a.) The time before the ball strikes the floor b.) The horizontal distance of the ball from the foot of the table

OpenStudy (anonymous):

the direction of initial velocity is x

OpenStudy (anonymous):

so the vertical movement is free fall with the initial velocity 0m/s equation：Y: $1/2\times g \times t ^{2} =1m$

OpenStudy (anonymous):

Rearrange haijon's expression to find the time of flight. and then use x=vt with v=3 and the time you've previously solved for to find the horizontal distance.

OpenStudy (anonymous):

t=$\sqrt{2h/g}$ h=1m g=9.8 m/$s ^{2}$


text:
mersenneforum.org > Math Question about a mersenne-number property
 Register FAQ Search Today's Posts Mark Forums Read

2011-03-08, 17:44   #23
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by Batalov ...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ?
best for length on a line I could fine is this (for what you do in the x and x2 parts):
Code:
Mod(Mod(2^a+2^b,n)^2,n)
it also appears faster on my machine at the same a b and n values I used in my test.

Last fiddled with by science_man_88 on 2011-03-08 at 17:54

2011-03-08, 18:52   #24
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by sascha77 No. This is false. set p=11 ->$n=2^{p}-1 = 2047$ for this: $(2^{11}+2^{1})^{2046} \equiv (\;(2^{11} + 2^{1})\;mod(\;2047)\;)^{2046} \equiv 3^{2046} \equiv 1013\;(mod\; 2047)$
1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23

2011-03-08, 21:04   #25
CRGreathouse

Aug 2006

135438 Posts

Quote:
 Originally Posted by Batalov ...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ?
Mod(2,n)^a + Mod(2,n)^b. For the square of that, use (Mod(2,n)^a + Mod(2,n)^b)^2. You can reduce the caculations in the inner loop by lifting Mod(2,n) and Mod(2,n)^a out of the b loop: go from
Code:
{forprime(p=2,3000,
if(!isprime(n=2^p-1),
print(p);
for(a=1,p-1,
for(b=0,a-1,
x=(2^a+2^b)%n;
x2=(x^2)%n;
c=x;
for(i=1,p,
c=(c^2)%n
);
if(c==x2,print("found: a="a", b="b))
)
)
)
)}
to
Code:
{forprime(p=2,3000,
if(!isprime(n=2^p-1),
print(p);
two=Mod(2,n);
for(a=1,p-1,
t=two^a;
for(b=0,a-1,
c=t+two^b;
x2=c^2;
c=c^(2^p);
if(c==x2,print("found: a="a", b="b))
)
)
)
)}

Last fiddled with by CRGreathouse on 2011-03-08 at 21:11

 2011-03-08, 21:51 #26 sascha77     Jan 2010 germany 2·13 Posts I think we do not need to calculate more. Because I found out that if someone will find a counterexample with an a and an b so the other a's an b's must also fail for these n=2^p-1 (p prime). And the following: $3^{n-1} \equiv\;1\;(mod\; n)$ was from many people already intensive searched and no one has still found an composite number n=2^p-1 that holds the above congruation. So if we continue searching we would not find an counterexample because 3 = (2^0+2^1) I will in short try to give the proof about that.
 2011-03-09, 00:10 #27 sascha77     Jan 2010 germany 2×13 Posts I will now try to proof that if somebody have found an composite number n=2^p-1 (with p is prime) so that the congruence 'fails' then it must also fail for all the other a' and b's (with the same n) I did my best, but there are certainly some errors in it. So I will be glad if someone find these errors (in the proof) and let me now. I hope that these are not evil ones ;-) Ok. First I will introduce an equivalent conjecture which is much better : (1) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$ is the above congruation false with $n=2^{p}-1$ if $n$ is not prime. (I do not want to proof that this conjecture is equivalent, we canjust take it as new conjecture) --------------------------------------------------------------------- Propositions: (2) If we add the two variables $a$ and $b$ with an same value k then the result will be the same. (Regardless if $n$ is prime or not) $n=2^{p}-1$ ,$p$ is prime $(2^{a+k}+2^{b+k})^{n-1}\; \equiv\; (2^{a}+2^{b})^{n-1}\;(\;mod\;n)$ for every $k \in N$ the congruence is true. ------------------------------------------------------------------ (3): If the congruence (1) is true for an a=a' and an b=b' then the congruence must also be true for a=a' and b=(b'+1) This means the variable a is the same but the variable b is by one greater as before. $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ---> $(2^{a}+2^{b+1})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ -------------------------------------------------------------------- ****************************************************** proof of (2): $ (2^{a}+2^{b})^{n-1} \equiv \; (2^{a}+2^{b}) * (2^{a}+2^{b})^{n-2}$ $ \equiv \; 2^{a} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^{a}+2^{b})^{n-2}$ $\equiv \; 2^{a} * 1 * (2^{a}+2^{b})^{n-2} + 2^{b} * 1 * (2^{a}+2^{b})^{n-2} \equiv \; 2^{a} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} \;$ $\equiv \;2^{a} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2}$ $\equiv \; 2^{a} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2} + 2^{b} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2}$ $\equiv \; 2^{a+k} * ( 2^{a+k}+2^{b+k})^{n-2} + 2^{b+k} * (2^{a+k}+2^{b+k})^{n-2}$ $\equiv (2^{a+k}+2^{b+k})^{n-1}$ ****************************************************** proof of (3) : lets Define a function$f(x) = 2*x-1$ if we now do the function with the left and right side we get: $f( (2^{a}+2^{b})^{n-1}) \; \equiv\; f(1) \;(\;mod\;n)$ $2*(2^{a}+2^{b})^{n-1}-1\; \equiv\; 1 \;(\;mod\;n)$ The congruence is still the neutral element 1. And if we have found an a and an b so that the congruence is true: $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0. We then have : $(2^{0}+2^{b'})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ----> $(2^{0}+2^{b'})^{n}\; \equiv\; 2^{0}+2{b'} \;(\;mod\;n)$ Now we use also here the function f(x): (First multiply then subtract one) $2^{0}+2^{b'} \;(\;mod\;n)\; / * 2$ $\equiv \; 2^{1}+2^{b'+1} \;(\;mod\;n)\;$ Now subtract the number 1: $\equiv \; 2^{1}+2^{b'+1} \;\;-1 \; \equiv \; 2^{0}+2^{b'+1} \;(\;mod\;n)\; $ $\equiv (2^{0}+2^{b'+1})^{n} \; (\;mod \; n)$ Then we shift the exponents both back so that $2^{(0)}$ gets to its initial value $2^{(a)}$ we then have: $ \equiv (2^{a}+2^{b+1})^{n} \; (\;mod \; n)$ And if we do recursive this method we can make the distance between a and b as big as we want. ******************************************************* Last fiddled with by sascha77 on 2011-03-09 at 00:22
2011-03-09, 00:13   #28
sascha77

Jan 2010
germany

2·13 Posts

Quote:
 Originally Posted by science_man_88 1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23
I do not know exactly what you mean.
Is it possible that you show me your idea with an example ?

thanks.

2011-03-09, 02:53   #29
wblipp

"William"
May 2003
Near Grandkid

2×1,187 Posts

Quote:
 Originally Posted by sascha77 I think we do not need to calculate more.
Are you still working on this? See Bob Silverman's hint in post #3. It follows VERY quickly from that hint.

 2011-03-09, 02:56 #30 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1005910 Posts Are there any* known false witnesses for 2p-1 with prime p>11? ____________ *any, not necessarily with Hamming weight 2 EDIT: yes. I've stepped out of pfgw (which only works with bases <=255) and with Pari, 'found' one: 349 for 2^29-1. It is probably known. And then many for 2^23-1 and many more for 2^29-1... Last fiddled with by Batalov on 2011-03-09 at 03:46
2011-03-09, 03:43   #31
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by sascha77 I will now try to proof that if somebody have found an composite number n=2^p-1 (with p is prime) so that the congruence 'fails' then it must also fail for all the other a' and b's (with the same n) I did my best, but there are certainly some errors in it. So I will be glad if someone find these errors (in the proof) and let me now. I hope that these are not evil ones ;-) Ok. First I will introduce an equivalent conjecture which is much better : (1) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$ is the above congruation false with $n=2^{p}-1$ if $n$ is not prime. (I do not want to proof that this conjecture is equivalent, we canjust take it as new conjecture) --------------------------------------------------------------------- Propositions: (2) If we add the two variables $a$ and $b$ with an same value k then the result will be the same. (Regardless if $n$ is prime or not) $n=2^{p}-1$ ,$p$ is prime $(2^{a+k}+2^{b+k})^{n-1}\; \equiv\; (2^{a}+2^{b})^{n-1}\;(\;mod\;n)$ for every $k \in N$ the congruence is true.

You are disguising what is going on. All you have done is multiply
(2^a + 2^b)^(n-1) by 2^(k(n-1)) [all mod n]

But 2^(n-1) = 1 for all n = 2^p-1, even when 2^p-1 isn't prime, because
2 is always a false withness for 2^p-1.

I will look at the rest later. I am sleepy at the moment.

2011-03-09, 06:32   #32
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by Batalov Are there any* known false witnesses for 2p-1 with prime p>11?
Sure -- are there any composite 2p - 1, p > 11 prime, lacking false witnesses?

Depending on how you count it, 2[SUP]23[/SUP] - 1 has 1056, 1057, or 1058 false witnesses. 2[SUP]29[/SUP] - 1 has over a hundred thousand.

 2011-03-09, 14:07 #33 ATH Einyen     Dec 2003 Denmark 19·181 Posts I find the subject of witness and false/non-witness for Miller-Rabin test interesting. I found this paper with 2 conjectures on oeis.org: http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf http://oeis.org/A090659 His conjectures includes 1 as a non-witness for all numbers. Conjecture 1 checks out for all 168,331 n=p*q<10^6 where p,q are distinct primes. Conjecture 2 checks out for n=p*q<5*10^8 p,q primes where p=2r+1, q=4r+1=2p-1 and r odd. I have my own conjecture for n=p^2, p prime: The number of non-witnesses is p-1, and they are pairwise symmetric about p^2/2, the 1st is 1 and the p-1'th is p^2-1. If we call the k'th non-witness nw(k) then: nw(k)+nw(p-k) = p^2. It is only based on computations not on heuristics or any attempt to prove it. Last fiddled with by ATH on 2011-03-09 at 14:11

 Similar Threads Thread Thread Starter Forum Replies Last Post aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 Thiele Math 18 2010-05-23 05:35 kurtulmehtap Math 12 2010-05-03 14:02 arithmeticae Lounge 5 2008-10-27 06:15 T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 23:03.

Mon Feb 6 23:03:54 UTC 2023 up 172 days, 20:32, 1 user, load averages: 1.15, 1.11, 1.05


text:
### A Set of Coordinate instances

No. 190

#### Inserting Coordinate instances into a Set.

 Q: Create a Set of Coordinate instances including duplicates. Iterate over this set and write each value to System.out in a similar fashion to Inserting strings into a Set. . Compare your output to the corresponding example Inserting strings into a Set. . Did you expect this behaviour? Explain this result and a solution. A: Our code is very similar to Inserting strings into a Set. : final Set points = new HashSet(); points.add(new Coordinate(1, 2)); points.add(new Coordinate(4, 1)); points.add(new Coordinate(1, 2)); // Equal to first Object // Iterate over all inserted coordinates System.out.println("The set contains " + points.size() + " elements:"); for (final Coordinate c : points) { System.out.println(c.toString()); }Since we do have set semantics we expect the duplicate coordinate value (1|2) to be dropped and thus to appear only once. So our set should contain {(4|1), (1|2)}. We however see the duplicate object appearing on standard output: The set contains 3 elements: (4|1) (1|2) (1|2)This is due to our own fault not providing a hashCode() implementation being compatible to our overridden equals() method. Consider: final Coordinate c12 = new Coordinate(1, 2), c12Duplicate = new Coordinate(1, 2); System.out.println("c12.hashCode() and c12Duplicate.hashCode():"+ c12.hashCode() + "," + c12Duplicate.hashCode());This yields the following output:c12.hashCode() and c12Duplicate.hashCode():1334574952,1882008996Apparently the two instances c12 and c12Duplicate are equal to each other. Their hash codes however are different clearly violating the contract being described in Java Collections - hashCode() and equals(). The values actually stem from hashCode() being defined in our superclass Object. The former exercise Inserting strings into a Set. involved instances of class String having well defined equals() and hashCode() implementations. To resolve this issue we thus have to override not just equals() but hashCode() as well: public class Coordinate { private int x, y; ... @Override public int hashCode() { // See last answer (06/16/2014) in // http://stackoverflow.com/questions/16629893/good-hashcode-implementation return Long.valueOf(x * 31 + y).hashCode(); } }This yields:c12.hashCode() and c12Duplicate.hashCode():33,33And finally:The set contains 2 elements: (1|2) (4|1)